Discussiones Mathematicae Graph Theory 27(1) (2007) 69-82
doi: 10.7151/dmgt.1345

[BIBTex] [PDF] [PS]

NONSINGULAR UNICYCLIC MIXED GRAPHS WITH AT MOST THREE EIGENVALUES GREATER THAN TWO

Shi-Cai Gong1,2  and  Yi-Zheng Fan1

1School of Mathematics and Computational Science
Anhui University
Hefei, Anhui 230039, P.R. China

2Department of Mathematics and Physics
Anhui University of Science and Technology
Anhui, Huainan 232001
e-mail: fanyz@ahu.edu.cn
   e-mail: gongsc@ahuu.edu.cn

Abstract

This paper determines all nonsingular unicyclic mixed graphs on at least nine vertices with at most three Laplacian eigenvalues greater than two.

Keywords: unicyclic graph, mixed graph, Laplacian eigenvalue, matching number, spectrum.

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, accepted for publication.
[5] Y.-Z. Fan, On spectral integral variations of mixed graphs, Linear Algebra Appl. 347 (2003) 307-316, doi: 10.1016/S0024-3795(03)00575-5.
[6] M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory, Czechoslovak Math. J. 25 (1975) 619-633.
[7] R. Grone, R. Merris and V.S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990) 218-238, doi: 10.1137/0611016.
[8] 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.
[9] R.A. Horn and C.R. Johnson, Matrix analysis (Cambridge University Press, 1985).
[10] 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.
[11] 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 23 September 2005
Revised 29 November 2006