ABSTRACT
Adjacency matrices are square (and typically sparse) V × V or E × E symmetric matrices that reect the adjacencies between vertices or edges in graphs (V = the number of vertices, E = the number of edges). Variants of adjacency matrices, called augmented adjacency matrices (Randić, 1991a), are adjacency matrices that possess nonzero values on the main diagonal (Trinajstić, 1983, 1992; Cvetković et al., 1995). Once the adjacency matrix is known, the related graph can easily be reconstructed. The structure of the adjacency matrix depends, however, on the labeling of a graph. Therefore, the adjacency matrix is not a graph invariant. An invariant of a graph G is a number associated with G that has the same value for any graph isomorphic to G (Harary, 1971).
