The infimum of the least eigenvalues of all finite induced subgraphs of an infinite graph is defined to be its least eigenvalue. In [P.J. Cameron, J.M. Goethals, J.J. Seidel and E.E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976) 305-327], the class of all finite graphs whose least eigenvalues ≥ −2 has been classified: (1) If a (finite) graph is connected and its least eigenvalue is at least −2, then either it is a generalized line graph or it is represented by the root system E8. In [A. Torgašev, A note on infinite generalized line graphs, in: Proceedings of the Fourth Yugoslav Seminar on Graph Theory, Novi Sad, 1983 (Univ. Novi Sad, 1984) 291- 297], it has been found that (2) any countably infinite connected graph with least eigenvalue ≥ −2 is a generalized line graph. In this article, the family of all generalized line graphs-countable and uncountable-is described algebraically and characterized structurally and an extension of (1) which subsumes (2) is derived.
@article{bwmeta1.element.doi-10_7151_dmgt_1691,
author = {Gurusamy Rengasamy Vijayakumar},
title = {Characterizations of the Family of All Generalized Line Graphs-Finite and Infinite-and Classification of the Family of All Graphs Whose Least Eigenvalues >= -2},
journal = {Discussiones Mathematicae Graph Theory},
volume = {33},
year = {2013},
pages = {637-648},
zbl = {1295.05197},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1691}
}
Gurusamy Rengasamy Vijayakumar. Characterizations of the Family of All Generalized Line Graphs-Finite and Infinite-and Classification of the Family of All Graphs Whose Least Eigenvalues ≥ −2. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 637-648. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1691/
[1] L.W. Beineke, Characterization of derived graphs, J. Combin. Theory 9 (1970) 129-135. doi:10.1016/S0021-9800(70)80019-9[Crossref]
[2] P.J. Cameron, J.M. Goethals, J.J. Seidel and E.E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976) 305-327. doi:10.1016/0021-8693(76)90162-9[Crossref] | Zbl 0337.05142
[3] P.D. Chawathe and G.R. Vijayakumar, A characterization of signed graphs represented by root system D1, European J. Combin. 11 (1990) 523-533. | Zbl 0764.05090
[4] D. Cvetković, M. Doob and S. Simić, Generalized line graphs, J. Graph Theory 5 (1981) 385-399. doi:10.1002/jgt.3190050408[Crossref] | Zbl 0475.05061
[5] D. Cvetković, P. Rowlinson and S. Simić, Graphs with least eigenvalue −2: a new proof of the 31 forbidden subgraphs theorem, Des. Codes Cryptogr. 34 (2005) 229-240. doi:10.1007/s10623-004-4856-5[Crossref] | Zbl 1063.05090
[6] F. Hirsch and G. Lacombe, Elements of Functional Analysis (Springer-Verlag, New York, 1999). doi:10.1007/978-1-4612-1444-1[Crossref] | Zbl 0924.46001
[7] A.J. Hoffman, On graphs whose least eigenvalue exceeds −1 − √2, Linear Algebra Appl. 16 (1977) 153-165. doi:10.1016/0024-3795(77)90027-1[Crossref]
[8] J. Krausz, D´emonstration nouvelle d’une th´eor`eme de Whitney sur les r´eseaux , Mat. Fiz. Lapok 50 (1943) 75-89.
[9] S.B. Rao, N.M. Singhi and K.S. Vijayan, The minimal forbidden subgraphs for generalized line graphs, Combinatorics and Graph Theory, Calcutta, 1980 S.B. Rao, Ed., Springer-Verlag, Lecture Notes in Math. 885 (1981) 459-472.
[10] A. Torgašev, A note on infinite generalized line graphs, in: Proceedings of the Fourth Yugoslav Seminar on Graph Theory, Novi Sad, 1983, D. Cvetković, I. Gutman, T. Pisanski, and R. Tošić (Ed(s)), (Univ. Novi Sad, 1984) 291-297.
[11] A. Torgašev, Infinite graphs with the least limiting eigenvalue greater than −2, Linear Algebra Appl. 82 (1986) 133-141. doi:10.1016/0024-3795(86)90146-1[Crossref] | Zbl 0611.05040
[12] A.C.M. van Rooij and H.S. Wilf, The interchange graphs of a finite graph, Acta Math. Acad. Sci. Hungar. 16 (1965) 263-269. doi:10.1007/BF01904834[Crossref] | Zbl 0139.17203
[13] G.R. Vijayakumar, A characterization of generalized line graphs and classification of graphs with least eigenvalue > −2, J. Comb. Inf. Syst. Sci. 9 (1984) 182-192. | Zbl 0629.05046
[14] G.R. Vijayakumar, Equivalence of four descriptions of generalized line graphs, J. Graph Theory 67 (2011) 27-33. doi:10.1002/jgt.20509[Crossref] | Zbl 1226.05185
[15] D.B. West, Introduction to Graph Theory, Second Edition (Prentice Hall, New Jersey, USA, 2001).