PDF
Discussiones Mathematicae Graph Theory 27(2) (2007)
373-384
DOI: https://doi.org/10.7151/dmgt.1368
ON THE SECOND LARGEST EIGENVALUE OF A MIXED GRAPH
Jun Zhou, Yi-Zheng Fan and Yi Wang
School of Mathematics and Computation Sciences
Anhui University, Hefei 230039, P.R. China
e-mail: {fanyz,zhoujun,wangy}@ahu.edu.cn
Abstract
Let G be a mixed graph. We discuss the relation between the second largest eigenvalue λ2(G) and the second largest degree d2(G), and present a sufficient condition for λ2(G) ≥ d2(G).Keywords: mixed graph, Laplacian eigenvalue, degree.
2000 Mathematics Subject Classification: 05C50, 15A18.
References
[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. |
[2] | R.B. Bapat, J.W. Grossman and D.M. Kulkarni, Edge version of the matrix tree theorem for trees, Linear and Multilinear Algebra 47 (2000) 217-229, doi: 10.1080/03081080008818646. |
[3] | Y.-Z. Fan, Largest eigenvalue of a unicyclic mixed graph, Applied Mathematics A Journal of Chinese Universities (English Series) 19 (2004) 140-148. |
[4] | Y.-Z. Fan, On the least eigenvalue of a unicyclic mixed graph, Linear and Multilinear Algebra 53 (2005) 97-113, doi: 10.1080/03081080410001681540. |
[5] | Y.-Z. Fan, On spectral integral variations of mixed graphs, Linear Algebra Appl. 374 (2003) 307-316, doi: 10.1016/S0024-3795(03)00575-5. |
[6] | M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298-305. |
[7] | M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory, Czechoslovak Math. J. 25 (1975) 619-633. |
[8] | R. Grone and R. Merris, The Laplacian spectrum of a graph II, SIAM J. Discrete Math. 7 (1994) 221-229, doi: 10.1137/S0895480191222653. |
[9] | J.-M. Guo and S.-W. Tan, A relation between the matching number and the Laplacian spectrum of a graph, Linear Algebra Appl. 325 (2001) 71-74, doi: 10.1016/S0024-3795(00)00333-5. |
[10] | R.A. Horn and C.R. Johnson, Matrix Analysis (Cambridge Univ. Press, Cambridge, 1985). |
[11] | 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. |
[12] | J.-S. Li and Y.-L. Pan, A note on the second largest eigenvalue of the Laplacian matrix of a graph, Linear and Multilinear Algebra 48 (2000) 117-121, doi: 10.1080/03081080008818663. |
[13] | R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1998) 143-176, doi: 10.1016/0024-3795(94)90486-3. |
[14] | 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. |
[15] | 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. |
[16] | X.-D. Zhang and R. Luo, The Laplacian eigenvalues of a mixed graph, Linear Algebra Appl. 353 (2003) 109-119, doi: 10.1016/S0024-3795(02)00509-8. |
Received 29 May 2006
Revised 12 September 2006
Accepted 12 September 2006
Close