Discussiones Mathematicae Graph Theory 27(2) (2007) 373-384
doi: 10.7151/dmgt.1368

[BIBTex] [PDF] [PS]

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