PDF
Discussiones Mathematicae Graph Theory 33(4) (2013)
637-648
DOI: https://doi.org/10.7151/dmgt.1691
Characterizations of the Family of All Generalized Line Graphs---Finite and Infinite---and Classification of the Family of All Graphs Whose Least Eigenvalues ≥-2
| Gurusamy Rengasamy Vijayakumar
School of Mathematics |
Abstract
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. Torgasev, 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.
Keywords: generalized line graph, enhanced line graph, representation of a graph, extended line graph, least eigenvalue of a graph
2010 Mathematics Subject Classification: 05C75, 05C63.
References
| [1] | L.W. Beineke, Characterization of derived graphs, J. Combin. Theory 9 (1970) 129--135, doi: 10.1016/S0021-9800(70)80019-9. |
| [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. |
| [3] | P.D. Chawathe and G.R. Vijayakumar, A characterization of signed graphs represented by root system D∞, European J. Combin. 11 (1990) 523--533. |
| [4] | D. Cvetković, M. Doob and S. Simić, Generalized line graphs, J. Graph Theory 5 (1981) 385--399, doi: 10.1002/jgt.3190050408. |
| [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. |
| [6] | F. Hirsch and G. Lacombe, Elements of Functional Analysis (Springer-Verlag, New York, 1999). |
| [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. |
| [8] | J. Krausz, Démonstration nouvelle d'une théorème de Whitney sur les réseaux, 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, ed(s), D. Cvetković, I. Gutman, T. Pisanski, and R. Tošić 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. |
| [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. |
| [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. |
| [14] | G.R. Vijayakumar, Equivalence of four descriptions of generalized line graphs, J. Graph Theory 67 (2011) 27--33, doi: 10.1002/jgt.20509. |
| [15] | D.B. West, Introduction to Graph Theory, Second Edition (Prentice Hall, New Jersey, USA, 2001). |
Received 28 December 2011
Revised 15 July 2012
Accepted 16 July 2012
Close