The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic
Yi Wang ; Yi-Zheng Fan ; Xiao-Xin Li ; Fei-Fei Zhang
Discussiones Mathematicae Graph Theory, Tome 35 (2015), p. 249-260 / Harvested from The Polish Digital Mathematics Library

A graph in a certain graph class is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum among all graphs in that class. Bell et al. have identified a subclass within the connected graphs of order n and size m in which minimizing graphs belong (the complements of such graphs are either disconnected or contain a clique of size n/2 ). In this paper we discuss the minimizing graphs of a special class of graphs of order n whose complements are connected and contains exactly one cycle (namely the class Ucn of graphs whose complements are unicyclic), and characterize the unique minimizing graph in Ucn when n ≥ 20.

Publié le : 2015-01-01
EUDML-ID : urn:eudml:doc:271086
@article{bwmeta1.element.doi-10_7151_dmgt_1796,
     author = {Yi Wang and Yi-Zheng Fan and Xiao-Xin Li and Fei-Fei Zhang},
     title = {The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {35},
     year = {2015},
     pages = {249-260},
     zbl = {1311.05119},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1796}
}
Yi Wang; Yi-Zheng Fan; Xiao-Xin Li; Fei-Fei Zhang. The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 249-260. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1796/

[1] F.K. Bell, D. Cvetković, P. Rowlinson and S. Simić, Graph for which the least eigenvalues is minimal, I , Linear Algebra Appl. 429 (2008) 234-241. doi:10.1016/j.laa.2008.02.032[Crossref] | Zbl 1149.05030

[2] F.K. Bell, D. Cvetković, P. Rowlinson and S. Simić, Graph for which the least eigenvalues is minimal, II , Linear Algebra Appl. 429 (2008) 2168-2179. doi:10.1016/j.laa.2008.06.018[Crossref] | Zbl 1144.05313

[3] D. Cvetković and P. Rowlinson, The largest eigenvalues of a graph: a survey, Linear Multilinear Algebra 28 (1990) 3-33. doi:10.1080/03081089008818026[Crossref] | Zbl 0744.05031

[4] D. Cvetković, P. Rowlinson and S. Simić, Spectral Generalizations of Line Graphs: on Graph with Least Eigenvalue −2 (London Math. Soc., LNS 314, Cambridge Univ. Press, 2004). | Zbl 1061.05057

[5] Y.-Z. Fan, Y. Wang and Y.-B. Gao, Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread, Linear Algebra Appl. 429 (2008) 577-588. doi:10.1016/j.laa.2008.03.012[WoS][Crossref] | Zbl 1143.05053

[6] Y.-Z. Fan, F.-F Zhang and Y. Wang, The least eigenvalue of the complements of trees, Linear Algebra Appl. 435 (2011) 2150-2155. doi:10.1016/j.laa.2011.04.011[WoS][Crossref]

[7] Y. Hong and J. Shu, Sharp lower bounds of the least eigenvalue of planar graphs, Linear Algebra Appl. 296 (1999) 227-232. doi:10.1016/S0024-3795(99)00129-9[Crossref]

[8] R. Liu, M. Zhai and J. Shu, The least eigenvalues of unicyclic graphs with n vertices and k pendant vertices, Linear Algebra Appl. 431 (2009) 657-665. doi:10.1016/j.laa.2009.03.016[WoS][Crossref] | Zbl 1169.05349

[9] M. Petrović, B. Borovićanin and T. Aleksić, Bicyclic graphs for which the least eigenvalue is minimum, Linear Algebra Appl. 430 (2009) 1328-1335. doi:10.1016/j.laa.2008.10.026[WoS][Crossref] | Zbl 1194.05093

[10] M. Petrović, T. Aleksić and S. Simić, Further results on the least eigenvalue of connected graphs, Linear Algebra Appl. 435 (2011) 2303-2313. doi:10.1016/j.laa.2011.04.030[WoS][Crossref] | Zbl 1222.05174

[11] Y.-Y. Tan and Y.-Z. Fan, The vertex (edge) independence number, vertex (edge) cover number and the least eigenvalue of a graph, Linear Algebra Appl. 433 (2010) 790-795. doi:10.1016/j.laa.2010.04.009[Crossref][WoS] | Zbl 1214.05085

[12] Y. Wang, Y. Qiao and Y.-Z. Fan, On the least eigenvalue of graphs with cut vertices, J. Math. Res. Exposition 30 (2010) 951-956. | Zbl 1240.05203

[13] Y. Wang and Y.-Z. Fan, The least eigenvalue of a graph with cut vertices, Linear Algebra Appl. 433 (2010) 19-27. doi:10.1016/j.laa.2010.01.030[WoS][Crossref]

[14] M.-L. Ye, Y.-Z. Fan and D. Liang, The least eigenvalue of graphs with given con- nectivity, Linear Algebra Appl. 430 (2009) 1375-1379. doi:10.1016/j.laa.2008.10.031 [Crossref]