An upper bound on the Laplacian spectral radius of the signed graphs
Hong-Hai Li ; Jiong-Sheng Li
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 345-359 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In this paper, we established a connection between the Laplacian eigenvalues of a signed graph and those of a mixed graph, gave a new upper bound for the largest Laplacian eigenvalue of a signed graph and characterized the extremal graph whose largest Laplacian eigenvalue achieved the upper bound. In addition, an example showed that the upper bound is the best in known upper bounds for some cases.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270323 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1410,
     author = {Hong-Hai Li and Jiong-Sheng Li},
     title = {An upper bound on the Laplacian spectral radius of the signed graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {345-359},
     zbl = {1156.05035},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1410}
}

Hong-Hai Li; Jiong-Sheng Li. An upper bound on the Laplacian spectral radius of the signed graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 345-359. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1410/

[000] [1] R.B. Bapat, J.W. Grossman and D.M. Kulkarni, Generalized matrix tree theorem for mixed graphs, Linear and Multilinear Algebra 46 (1999) 299-312, doi: 10.1080/03081089908818623. | Zbl 0940.05042

[001] [2] F. Chung, Spectral Graph Theory (CMBS Lecture Notes. AMS Publication, 1997).

[002] [3] D.M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs (Academic Press, New York, 1980). | Zbl 0458.05042

[003] [4] J.M. Guo, A new upper bound for the Laplacian spectral radius of graphs, Linear Algebra Appl. 400 (2005) 61-66, doi: 10.1016/j.laa.2004.10.022. | Zbl 1062.05091

[004] [5] F. Harary, On the notion of balanced in a signed graph, Michigan Math. J. 2 (1953) 143-146, doi: 10.1307/mmj/1028989917.

[005] [6] R.A. Horn and C.R. Johnson, Matrix Analysis (Cambridge Univ. Press, 1985). | Zbl 0576.15001

[006] [7] Y.P. Hou, J.S. Li and Y.L. Pan, On the Laplacian eigenvalues of signed graphs, Linear and Multilinear Algebra 51 (2003) 21-30, doi: 10.1080/0308108031000053611. | Zbl 1020.05044

[007] [8] L.L. Li, A simplified Brauer's theorem on matrix eigenvalues, Appl. Math. J. Chinese Univ. (B) 14 (1999) 259-264, doi: 10.1007/s11766-999-0034-x. | Zbl 0935.15018

[008] [9] R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197 (1994) 143-176, doi: 10.1016/0024-3795(94)90486-3. | Zbl 0802.05053

[009] [10] T.F. Wang, Several sharp upper bounds for the largest Laplacian eigenvalues of a graph, to appear.

[010] [11] T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982) 47-74, doi: 10.1016/0166-218X(82)90033-6. | Zbl 0476.05080

[011] [12] X.D. Zhang, Two sharp upper bounds for the Laplacian eigenvalues, Linear Algebra Appl. 376 (2004) 207-213, doi: 10.1016/S0024-3795(03)00644-X. | Zbl 1037.05032

[012] [13] 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. | Zbl 1003.05073