# 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

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 4, page 637-648
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGurusamy 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 33.4 (2013): 637-648. <http://eudml.org/doc/267901>.

@article{GurusamyRengasamyVijayakumar2013,

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. 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.},

author = {Gurusamy Rengasamy Vijayakumar},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {generalized line graph; enhanced line graph; representation of a graph; extended line graph; least eigenvalue of a graph},

language = {eng},

number = {4},

pages = {637-648},

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},

url = {http://eudml.org/doc/267901},

volume = {33},

year = {2013},

}

TY - JOUR

AU - Gurusamy Rengasamy Vijayakumar

TI - Characterizations of the Family of All Generalized Line Graphs-Finite and Infinite-and Classification of the Family of All Graphs Whose Least Eigenvalues ≥ −2

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 4

SP - 637

EP - 648

AB - 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.

LA - eng

KW - generalized line graph; enhanced line graph; representation of a graph; extended line graph; least eigenvalue of a graph

UR - http://eudml.org/doc/267901

ER -

## References

top- [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] Zbl0337.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. Zbl0764.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] Zbl0475.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] Zbl1063.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] Zbl0924.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] Zbl0611.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] Zbl0139.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. Zbl0629.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] Zbl1226.05185
- [15] D.B. West, Introduction to Graph Theory, Second Edition (Prentice Hall, New Jersey, USA, 2001).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.