|
Internet Electronic Journal of Molecular Design - IEJMD, ISSN 1538-6414, CODEN IEJMAT
| ABSTRACT - Internet Electron. J. Mol. Des. August 2002, Volume 1, Number 8, 388-400 |
On Walk Counts and Complexity of General Graphs
Istvan Lukovits, Ante Milicevic, Sonja Nikolic, and Nenad Trinajstic
Internet Electron. J. Mol. Des. 2002, 1, 388-400
|
Abstract:
This report was motivated by a recent work of Gutman, Rucker and
Rucker on walks in simple molecular graphs, i.e., graphs without
multiple edges and loops. Three methods for counting walks in general
graphs, i.e., graphs with multiple bonds and loops, are presented: (i)
graphical method based on the Morgan summation procedure, (ii)
method based on augmented adjacency matrices of higher orders and
(iii) method based on eigenvalues and eigenvectors of augmented
adjacency matrices of higher orders. They represent extensions of the
methods discussed previously in the literature for simple graphs. The
total walk count (twc) was used as a measure for complexity of general
graphs. It is shown that twc indices increase with size, branching,
cyclicity, the number of loops and multiple bonds, and decrease with
symmetry of general graphs. The total walk count appears to be a
valuable tool to account for complexity for several types of molecular
graphs.
|