We review algebraic characterizations of molecular structures and in particular consider different matrices associated with a molecule as a source of novel graph invariants for use in structure-property and structure-activity studies. Such matrices can be classified as structure-explicit, structure-cryptic, and structure-implicit corresponding to a previous classification of molecular descriptors. In order to tame the proliferation of unwarranted topological indices, we propose requirements on indices and on the “source” matrices used for construction of molecular descriptors. Several structure-explicit and structure-implicit matrices are illustrated. A novel bond descriptorP′/P defined by the ratio of the number of paths in a graph G′, in which an edge is erased, and in the parent graphG′ is introduced. The derived bond-additive molecular P'/P index, which correlates well with the octane numbers in octanes, was found to be linearly related to the Wiener numbers.