Minimal least eigenvalue of connected graphs of order n and size m = n + k (5≤k≤8)

Abstract

The least eigenvalue of a connected graph is the least eigenvalue of its adjacency matrix. We characterize the connected graphs of order n and size n + k (5≤k≤8 and n>k + 5) with the minimal least eigenvalue.

Keywords

Least eigenvalue / adjacency matrix / graph

References

[1] Bell F K, Cvetković D, Rowlinson P, Simić S K. Graphs for which the least eigenvalue is minimal, I. Linear Algebra Appl, 2008, 429: 234–241

[2] Bell F K, Cvetković D, Rowlinson P, Simić S K. Graphs for which the least eigenvalue is minimal, II. Linear Algebra Appl, 2008, 429: 2168–2179, see also Erratum: from the editor-in-Chief, Linear Algebra Appl, 2010, 432: I–VI

[3] Bhattacharya A, Friedland S, Peled U N. On the first eigenvalue of bipartite graphs. Electron J Combin, 2008, 15(1): 144

[4] Cvetković D, Doob M, Sachs H. Spectra of Graphs. Berlin: Academic Press, 1980

[5] Cvetković D, Rowlinson P, Simić S K.Spectral Generalizations of Line Graphs. On graphs with least eigenvalue 2: Cambridge: Cambridge Univ Press, 2004

[6] Cvetković D, Rowlinson P, Simić S. An Introduction to the Theory of Graph Spectra. Cambridge: Cambridge Univ Press, 2010

[7] Doob M. A surprising property of the least eigenvalue of a graph. Linear Algebra Appl, 1982, 46: 1–7

[8] Fan Y, Wang Y, Gao Y. Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread. Linear Algebra Appl, 2008, 429: 577–588

[9] Petrović M, Aleksić T, Simić V. Further results on the least eigenvalue of connected graphs. Linear Algebra Appl, 2011, 435: 2303–2313

[10] Petrović M, Borovićanin B, Aleksić T. Bicyclic graphs for which the least eigenvalue is minimal. Linear Algebra Appl, 2009, 430: 1328–1335

[11] Voász L, Pelikán J. On the eigenvalues of trees. Period Math Hungar, 1973, 3: 175–182

[12] Wang Y, Fan Y. The least eigenvalue of a graph with cut vertices. Linear Algebra Appl, 2010, 433: 19–27

[13] Xu G. Upper bound on the least eigenvalue of unicyclic graphs. J Zhejiang Forestry College, 1998, 15(3): 304–309 (in Chinese)

[14] Zhai M, Liu R, Shu J. Minimizing the least eigenvalue of unicyclic graphs with fixed diameter. Discrete Math, 2010, 310: 947–955

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature