Premium
Common vertex matrix: A novel characterization of molecular graphs by counting
Author(s) -
Randić Milan,
Novič Marjana,
Plavšić Dejan
Publication year - 2013
Publication title -
journal of computational chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.907
H-Index - 188
eISSN - 1096-987X
pISSN - 0192-8651
DOI - 10.1002/jcc.23300
Subject(s) - combinatorics , mathematics , wheel graph , path graph , vertex (graph theory) , chordal graph , graph homomorphism , discrete mathematics , distance matrix , metric dimension , graph , 1 planar graph , graph power , line graph
We present a novel matrix representation of graphs based on the count of equal‐distance common vertices to each pair of vertices in a graph. The element ( i , j ) of this matrix is defined as the number of vertices at the same distance from vertices ( i , j ). As illustrated on smaller alkanes, these novel matrices are very sensitive to molecular branching and the distribution of vertices in a graph. In particular, we show that ordered row sums of these novel matrices can facilitate solving graph isomorphism for acyclic graphs. This has been illustrated on all undecane isomers C 11 H 24 having the same path counts (total of 25 molecules), on pair of graphs on 18 vertices having the same distance degree sequences (Slater's graphs), as well as two graphs on 21 vertices having identical several topological indices derived from information on distances between vertices. © 2013 Wiley Periodicals, Inc.