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

Abstract

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

How to cite

top

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 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [15] D.B. West, Introduction to Graph Theory, Second Edition (Prentice Hall, New Jersey, USA, 2001). 

NotesEmbed ?

top

You must be logged in to post comments.