Abstract
For periodic graphs, a special class of infinite, but locally finite graphs, an index theory is developed that can serve in classifying these graphs and that enables connections with various graph invariants as in the case of finite graphs. The index is defined with the aid of certain finite matrices that result rather canonically from reductions of the infinite adjacency operator due to the periodicity. As a central result we derive a sharp global lower bound for the index of any periodic graph.
Similar content being viewed by others
References
J. Von Below, A characteristic equation associated to an eigenvalue problem on C2 -networks, Lin. Alg. Appl. 71 (1985) 309–325.
A. Berman and R. J. Plemmons, Nonnegative matrices in the mathematical sciences, Academic Press New York, 1979.
N. L. Biggs, Algebraic graph theory, Cambridge Tracts Math. 67 Cambridge, 1967.
L. Collatz and U. Sinogowitz, Spektren endlicher Grafen, Abh. Math. Sem. Hamburg 21 (1957) 63–77.
L. Collatz, Spektren periodischer Graphen, Resultate der Mathematik 1 (1979) 42–53.
D. M. Cvetcovič, M. Doob and H. Sachs, Spectra of graphs, Academic Press New York, 1980.
D. Cvetcovic and P. Rowlinson, The largest eigenvalue of a graph: a survey, Lin. Multilin. Alg. 28 (1990) 3–33.
R. Halin, Graphentheorie I, Wiss. Buchges. Darmstadt, 1980.
A. Häussler, personal communication.
A. J. Hoffman, On eigenvalues and colourings of graphs, in: Graph theory and its applications, Academic Press New York 1970, pp. 79-92.
A. J. Hoffman, On limit points of spectral radii of nonnegative symmetric integral matrices, Lect. Not. Math. Vol. 303, Springer Verlag Heidelberg, New York, Berlin 1972, pp. 165–172.
M. Marcus and H. MINC, A survey of matrix theory and matrix inequalities, Allyn s& Bacon Boston, 1964.
H. Mlnc, Nonnegative matrices, Wiley & Sons Inc. New York, 1988.
B. Mohar and W. Woess, A survey on spectra of infinite graphs, Bull. London Math. Soc. 21 (1989) 209–234.
H. S. Wilf, The eigenvalues of a graph and its chromatic number, J. London Math. Soc. 42 (1967) 330–332.
R. J. Wilson, Introduction to graph theory, Oliver & Boyd Edinburgh, 1972.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
von Below, J. The Index of a Periodic Graph. Results. Math. 25, 198–223 (1994). https://doi.org/10.1007/BF03323406
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF03323406