The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic

• Autorzy: Yi Wang , Yi-Zheng Fan , Xiao-Xin Li , Fei-Fei Zhang
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

unicyclic graph; complement; adjacency matrix; least eigen- value

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 2
• Strony: 249-260

Daty

wydano

2015-05-01

otrzymano

2013-11-04

poprawiono

2014-06-06

zaakceptowano

2014-06-09

online

2015-04-18

Twórcy

autor

Yi Wang

• School of Mathematical Sciences Anhui University, Hefei 230601, P.R. China

autor

Yi-Zheng Fan

• School of Mathematical Sciences Anhui University, Hefei 230601, P.R. China

autor

Xiao-Xin Li

• Department of Mathematics and Computer Sciences Chizhou University, Chizhou 247000, P.R. China

autor

Fei-Fei Zhang

• School of Mathematical Sciences Anhui University, Hefei 230601, P.R. China

Bibliografia

• [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]
• [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]
• [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]
• [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).
• [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]
• [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]
• [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]
• [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]
• [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]
• [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.
• [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]

Identyfikatory

DOI

10.7151/dmgt.1796