PDF

Discussiones Mathematicae Graph Theory 30(1) (2010) 85-93
DOI: https://doi.org/10.7151/dmgt.1478

THE SIGNLESS LAPLACIAN SPECTRAL RADIUS OF GRAPHS WITH GIVEN NUMBER OF CUT VERTICES

Lin Cui  and Yi-Zheng Fan

School of Mathematical Sciences
Anhui University
Hefei 230039, P.R. China
e-mail: cuilin06@sina.com, fanyz@ahu.edu.cn

Abstract

In this paper, we determine the graph with maximal signless Laplacian spectral radius among all connected graphs with fixed order and given number of cut vertices.

Keywords: graph, cut vertex, signless Laplacian matrix, spectral radius.

2010 Mathematics Subject Classification: 05C50, 15A18.

References

[1]	W.N. Anderson and T.D. Morely, Eigenvalues of the Laplacian of a graph, Linear Multilinear Algebra 18 (1985) 141-145, doi: 10.1080/03081088508817681.
[2]	A. Berman and X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory (B) 83 (2001) 233-240, doi: 10.1006/jctb.2001.2052.
[3]	D. Cvetković, M. Doob and H. Sachs, Spectra of graphs, (third ed., Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995).
[4]	D. Cvetković, Signless Laplacians and line graphs, Bull. Acad. Serbe Sci. Ars. Cl. Sci. Math. Nat. Sci. Math. 131 (30) (2005) 85-92.
[5]	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.
[6]	E.R. van Dam and W. Haemers, Which graphs are determined by their spectrum? Linear Algebra Appl. 373 (2003) 241-272, doi: 10.1016/S0024-3795(03)00483-X.
[7]	M. Desai and V. Rao, A characterization of the smallest eigenvalue of a graph, J. Graph Theory 18 (1994) 181-194, doi: 10.1002/jgt.3190180210.
[8]	Y.-Z. Fan, B.-S. Tam and J. Zhou, Maximizing spectral radius of unoriented Laplacian matrix over bicyclic graphs of a given order, Linear Multilinear Algebra 56 (2008) 381-397, doi: 10.1080/03081080701306589.
[9]	M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298-305.
[10]	R. Grone and R. Merris, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990) 218-238, doi: 10.1137/0611016.
[11]	J.W. Grossman, D.M. Kulkarni and I. Schochetman, Algebraic graph theory without orientation, Linear Algebra Appl. 212/213 (1994) 289-307, doi: 10.1016/0024-3795(94)90407-3.
[12]	W. Haemer and E. Spence, Enumeration of cospectral graphs, Europ. J. Combin. 25 (2004) 199-211, doi: 10.1016/S0195-6698(03)00100-8.
[13]	Q. Li and K.-Q. Feng, On the largest eigenvalues of graphs, (in Chinese), Acta Math. Appl. Sin. 2 (1979) 167-175.
[14]	R. Merris, Laplacian matrices of graphs: A survey, Linear Algebra Appl. 197/198 (1994) 143-176, doi: 10.1016/0024-3795(94)90486-3.
[15]	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.
[16]	B.-S. Tam, Y.-Z. Fan and J. Zhou, Unoriented Laplacian maximizing graphs are degree maximal, Linear Algebra Appl. 429 (2008) 735-758, doi: 10.1016/j.laa.2008.04.002.
[17]	Shangwang Tan and Xingke Wang, On the largest eigenvalue of signless Laplacian matrix of a graph, Journal of Mathematical Reserch and Exposion 29 (2009) 381-390.
[18]	X.-D. Zhang and R. Luo, The Laplacian eigenvalues of a mixed graph, Linear Algebra Appl. 362 (2003) 109-119, doi: 10.1016/S0024-3795(02)00509-8.

Received 25 April 2008
Revised 2 January 2009
Accepted 12 March 2009