Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
mixed graphs; Laplacian eigenvectors
mixed graphs; Laplacian eigenvectors
Summary:
Let $G$ be a mixed graph. The eigenvalues and eigenvectors of $G$ are respectively defined to be those of its Laplacian matrix. If $G$ is a simple graph, [M. Fiedler: A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory, Czechoslovak Math. J. 25 (1975), 619–633] gave a remarkable result on the structure of the eigenvectors of $G$ corresponding to its second smallest eigenvalue (also called the algebraic connectivity of $G$). For $G$ being a general mixed graph with exactly one nonsingular cycle, using Fiedler’s result, we obtain a similar result on the structure of the eigenvectors of $G$ corresponding to its smallest eigenvalue.
References:
[1] R. B. Bapat, S. Pati: Algebraic connectivity and the characteristic set of a graph. Linear Multilinear Algebra 45 (1998), 247–273. DOI 10.1080/03081089808818590 | MR 1671627
[2] R. B. Bapat, J. W. Grossman, D. M. Kulkarni: Generalized matrix tree theorem for mixed graphs. Linear Multilinear Algebra 46 (1999), 299–312. DOI 10.1080/03081089908818623 | MR 1729196
[3] R. B. Bapat, J. W. Grossman, D. M. Kulkarni: Edge version of the matrix tree theorem for trees. Linear Multilinear Algebra 47 (2000), 217–229. DOI 10.1080/03081080008818646 | MR 1785029
[4] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications. Elsevier, New York, 1976. MR 0411988
[5] F. R. K. Chung: Spectral Graph Theory. Conference Board of the Mathematical Science, No. 92. Am. Math. Soc., Providence, 1997. MR 1421568
[6] Y.-Z. Fan: On spectra integral variations of mixed graph. Linear Algebra Appl. 374 (2003), 307–316. DOI 10.1016/S0024-3795(03)00575-5 | MR 2008794
[7] M. Fiedler: Algebraic connectivity of graphs. Czechoslovak Math. J. 23 (1973), 298–305. MR 0318007 | Zbl 0265.05119
[8] M. Fiedler: A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory. Czechoslovak Math. J. 25 (1975), 619–633. MR 0387321
[9] J. W. Grossman, D. M. Kulkarni, I. E. Schochetman: Algebraic graph theory without orientations. Linear Algebra Appl. 212/213 (1994), 289–308. MR 1306983
[10] J. M. Guo, S. W. Tan: A relation between the matching number and the Laplacian spectrum of a graph. Linear Algebra Appl. 325 (2001), 71–74. MR 1810095
[11] R. A. Horn, C. R. Johnson: Matrix Analysis. Cambridge Univ. Press, Cambridge, 1985. MR 0832183
[12] S. Kirkland, S. Fallat: Perron components and algebraic connectivity for weighted graphs. Linear Multilinear Algebra 44 (1998), 131–148. DOI 10.1080/03081089808818554 | MR 1674228
[13] S. Kirkland, M. Neumann, B. Shader: Characteristic vertices of weighted trees via Perron values. Linear Multilinear Algebra 40 (1996), 311–325. DOI 10.1080/03081089608818448 | MR 1384650
[14] L. S. Melnikov, V. G. Vizing: The edge chromatic number of a directed/mixed multi-graph. J. Graph Theory 31 (1999), 267–273. DOI 10.1002/(SICI)1097-0118(199908)31:4<267::AID-JGT1>3.3.CO;2-4 | MR 1698744
[15] R. Merris: Laplacian matrices of graphs: a survey. Linear Algebra Appl. 197/198 (1994), 143–176. MR 1275613 | Zbl 0802.05053
[16] B. Mohar: Some applications of Laplacian eigenvalues of graphs. In: Graph Symmetry, G. Hahn and G. Sabidussi (eds.), Kluwer, Dordrecht, 1997, pp. 225–275. MR 1468791
[17] X.-D. Zhang, J.-S. Li: The Laplacian spectrum of a mixed graph. Linear Algebra Appl. 353 (2002), 11–20. MR 1918746 | Zbl 1003.05073
Search
Partner of
