Discussiones Mathematicae Graph Theory 28(3) (2008) 487-499

ORDER UNICYCLIC GRAPHS ACCORDING TO SPECTRAL RADIUS OF UNORIENTED LAPLACIAN MATRIX

Yi-Zheng Fan

Key Laboratory of Intelligent Computing & Signal Processing
Ministry of Education of the People's Republic of China
Anhui University, Hefei 230039, P.R. China
e-mail: fanyz@ahu.edu.cn

Song Wu

School of Mathematics and Computation Sciences
Anhui University, Hefei, Anhui 230039, P.R. China

Abstract

The spectral radius of a graph is defined by that of its unoriented Laplacian matrix. In this paper, we determine the unicyclic graphs respectively with the third and the fourth largest spectral radius among all unicyclic graphs of given order.

Keywords: unicyclic graph, Laplacian matrix, spectral radius.

2000 Mathematics Subject Classification: 05C50, 15A18.

References

[1] R.B. Bapat, J.W. Grossmana and D.M. Kulkarni, Generalized matrix tree theorem for mixed graphs, Linear Multilinear Algebra 46 (1999) 299-312, doi: 10.1080/03081089908818623.
[2] D. Cvetković, P. Rowlinson and S.K. Simić, Signless Laplacians of finite graphs, Linear Algebra Appl. 423 (2007) 155-171, doi: 10.1016/j.laa.2007.01.009.
[3] Y.-Z. Fan, On spectral integral variations of mixed graph, Linear Algebra Appl. 374 (2003) 307-316, doi: 10.1016/S0024-3795(03)00575-5.
[4] Y.-Z. Fan, Largest eigenvalue of a unicyclic mixed graph, Appl. Math. J. Chinese Univ. (B) 19 (2004) 140-148, doi: 10.1007/s11766-004-0047-4.
[5] Y.-Z. Fan, On the least eigenvalue of a unicyclic mixed graph, Linear Multilinear Algebra 53 (2005) 97-113, doi: 10.1080/03081080410001681540.
[6] Y.-Z. Fan, H.-Y. Hong, S.-C. Gong and Y. Wang, Order unicyclic mixed graphs by spectral radius, Australasian J. Combin. 37 (2007) 305-316.
[7] Y.-Z. Fan, B.-S. Tam and J. Zhou, Maximizing spectral radius of unoriented Laplacian matrix over bicyclic graphs of a 798 given order, Linear and Multilinear Algebra (2007), , doi: 10.1080/03081080701306589.
[8] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298-305.
[9] J.W. Grossman, D.M. Kulkarni and I.E. Schochetman, Algebraic Graph Theory Without Orientation, Linear Algebra Appl. 212/213 (1994) 289-307, doi: 10.1016/0024-3795(94)90407-3.
[10] Y.-P. Hou, J.-S. Li and Y.-L. Pan, On the Laplacian eigenvalues of signed graphs, Linear Multilinear Algebra 51 (2003) 21-30, doi: 10.1080/0308108031000053611.
[11] R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1998) 143-176, doi: 10.1016/0024-3795(94)90486-3.
[12] B. Mohar, Some applications of Laplacian eigenvalues of graphs, in: Graph Symmetry (G. Hahn and G. Sabidussi Eds (Kluwer Academic Publishers, Dordrecht, 1997) 225-275.
[13] B.-S. Tam, Y.-Z. Fan and J. Zhou, Unoriented Laplacian maximizing graphs are degree maximal, Linear Algebra Appl. (2008), doi: 10.1016/j.laa.2008.04.002.
[14] X.-D. Zhang and J.-S. Li, The Laplacian spectrum of a mixed graph, Linear Algebra Appl. 353 (2002) 11-20, doi: 10.1016/S0024-3795(01)00538-9.
[15] X.-D. Zhang and Rong Luo, The Laplacian eigenvalues of mixed graphs, Linear Algebra Appl. 362 (2003) 109-119, doi: 10.1016/S0024-3795(02)00509-8.

Received 18 December 2007
Revised 13 May 2008
Accepted 13 May 2008