On kites, comets, and stars. Sums of eigenvector coefficients in (molecular) graphs.
Research output: Journal contributions › Journal articles › Research › peer-review
Standard
In: Zeitschrift fur Naturforschung - Section A Journal of Physical Sciences, Vol. 57, No. 3-4, 2002, p. 143-153.
Research output: Journal contributions › Journal articles › Research › peer-review
Harvard
APA
Vancouver
Bibtex
}
RIS
TY - JOUR
T1 - On kites, comets, and stars. Sums of eigenvector coefficients in (molecular) graphs.
AU - Rücker, Christoph
AU - Rücker, Getra
AU - Gutman, Ivan
PY - 2002
Y1 - 2002
N2 - Two graph invariants were encountered that form the link between (molecular) walk counts and eigenvalues of graph adjacency matrices. In particular, the absolute value of the sum of coefficients of the first or principal (normalized) eigenvector, s 1, and the analogous quantity s n, pertaining to the last eigenvector, appear in equations describing some limits (for infinitely long walks) of relative frequencies of several walk counts. Quantity s 1 is interpreted as a measure of mixedness of a graph, and s n, which plays a role for bipartite graphs only, is interpreted as a measure of the imbalance of a bipartite graph. Consequently, s n is maximal for star graphs, while the minimal value of s n is zero. Mixedness s 1 is maximal for regular graphs. Minimal values of s 1 were found by exhaustive computer search within the sample of all simple connected undirected n-vertex graphs, n ≤ 10: They are encountered among graphs called kites. Within the special sample of tree graphs (searched for n ≤ 20) so-called double snakes have maximal s 1, while the trees with minimal s 1 are so-called comets. The behaviour of stars and double snakes can be described by exact equations, while approximate equations for s 1 of kites and comets could be derived that are fully compatible with and allow to predict some pecularities of the results of the computer search. Finally, the discriminating power of s 1, determined within trees and 4-trees (alkanes), was found to be high.
AB - Two graph invariants were encountered that form the link between (molecular) walk counts and eigenvalues of graph adjacency matrices. In particular, the absolute value of the sum of coefficients of the first or principal (normalized) eigenvector, s 1, and the analogous quantity s n, pertaining to the last eigenvector, appear in equations describing some limits (for infinitely long walks) of relative frequencies of several walk counts. Quantity s 1 is interpreted as a measure of mixedness of a graph, and s n, which plays a role for bipartite graphs only, is interpreted as a measure of the imbalance of a bipartite graph. Consequently, s n is maximal for star graphs, while the minimal value of s n is zero. Mixedness s 1 is maximal for regular graphs. Minimal values of s 1 were found by exhaustive computer search within the sample of all simple connected undirected n-vertex graphs, n ≤ 10: They are encountered among graphs called kites. Within the special sample of tree graphs (searched for n ≤ 20) so-called double snakes have maximal s 1, while the trees with minimal s 1 are so-called comets. The behaviour of stars and double snakes can be described by exact equations, while approximate equations for s 1 of kites and comets could be derived that are fully compatible with and allow to predict some pecularities of the results of the computer search. Finally, the discriminating power of s 1, determined within trees and 4-trees (alkanes), was found to be high.
KW - Mathematics
KW - Eigenvector Coefficients
KW - Molecular Graphs
KW - Walks
UR - http://www.scopus.com/inward/record.url?scp=0036347081&partnerID=8YFLogxK
U2 - 10.1515/zna-2002-3-406
DO - 10.1515/zna-2002-3-406
M3 - Journal articles
VL - 57
SP - 143
EP - 153
JO - Zeitschrift fur Naturforschung - Section A Journal of Physical Sciences
JF - Zeitschrift fur Naturforschung - Section A Journal of Physical Sciences
SN - 0932-0784
IS - 3-4
ER -