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 (2015)

  • Volume: 35, Issue: 2, page 249-260
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Yi Wang, et al. "The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic." Discussiones Mathematicae Graph Theory 35.2 (2015): 249-260. <http://eudml.org/doc/271086>.

@article{YiWang2015,
abstract = {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.},
author = {Yi Wang, Yi-Zheng Fan, Xiao-Xin Li, Fei-Fei Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {unicyclic graph; complement; adjacency matrix; least eigen- value; least eigenvalue},
language = {eng},
number = {2},
pages = {249-260},
title = {The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic},
url = {http://eudml.org/doc/271086},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Yi Wang
AU - Yi-Zheng Fan
AU - Xiao-Xin Li
AU - Fei-Fei Zhang
TI - The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 249
EP - 260
AB - 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.
LA - eng
KW - unicyclic graph; complement; adjacency matrix; least eigen- value; least eigenvalue
UR - http://eudml.org/doc/271086
ER -

References

top
  1. [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] Zbl1149.05030
  2. [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] Zbl1144.05313
  3. [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] Zbl0744.05031
  4. [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). Zbl1061.05057
  5. [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] Zbl1143.05053
  6. [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. [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. [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] Zbl1169.05349
  9. [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] Zbl1194.05093
  10. [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] Zbl1222.05174
  11. [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] Zbl1214.05085
  12. [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. Zbl1240.05203
  13. [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. [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] 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.