ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 30(1) (2010) 85-93


Lin Cui  and Yi-Zheng Fan

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


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.


[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