×

Algebraic connectivity and the characteristic set of a graph. (English) Zbl 0944.05066

Summary: Let \(G\) be a connected weighted graph on the vertices \(1,2,\dots, n\) and \(L\) be the Laplacian matrix of \(G\). Let \(\mu\) be the second smallest eigenvalue of \(L\) and \(Y\) be an eigenvector corresponding to \(\mu\). A characteristic vertex is a vertex \(v\) such that \(Y(v)= 0\) and \(Y(w)\neq 0\) for some vertex \(w\) adjacent to \(v\). An edge \(e\) with end vertices \(v\), \(w\) is called a characteristic edge of \(G\) if \(Y(w)Y(v)< 0\). The charcteristic vertices and the characteristic edges together form the charactristic set of \(G\). We investigate the characteristic set of an arbitrary graph. The relation between the characteristic set and nonnegative matrix theory is exploited. Bounds are obtained on the cardinality of the characteristic set. It is shown that if \(G\) is a connected graph with \(n\) vertices and \(m\) edges then the characteristic set has at most \(m-n+2\) elements. We use the description of the Moore-Penrose inverse of the vertex-edge incidence matrix of a tree to derive a classical result of Fiedler for a tree. Furthermore, an analogous result is obtained for an eigenvector corresponding to any eigenvalue. We obtain a formula for the Moore-Penrose inverse of the incidence matrix of a unicyclic graph and give a complete description of characteristic vectors of a unicyclic graph. It is shown that the coordinates of a characteristic vector are unimodal along the cycle in the unicyclic graph if we begin with a vertex corresponding to the smallest coordinate.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1080/03081089708818496 · Zbl 0881.15005 · doi:10.1080/03081089708818496
[2] Bapat R. B., Encyclopedia of mathematics 64 (1997)
[3] Bondy J. A., Graph theory with applications (1976) · Zbl 1226.05083
[4] Fiedler M., Czech. Math. J 23 pp 298– (1973)
[5] Fiedler M., Czech. Math. J. 25 pp 607– (1975)
[6] Fiedler M., Czech. Math. J. 25 pp 619– (1975)
[7] Fiedler M., In: Combinatorics and Graph theory 25 pp 57– (1989)
[8] DOI: 10.1080/03081089508818389 · Zbl 0832.05082 · doi:10.1080/03081089508818389
[9] Grone R., Czech. Math. J. 37 pp 660– (1987)
[10] DOI: 10.1137/0611016 · Zbl 0733.05060 · doi:10.1137/0611016
[11] Horn R. A., Matrix analysis (1987)
[12] Kirkland S., Linear and Multilinear Algebra (1987)
[13] DOI: 10.1080/03081089608818448 · Zbl 0866.05041 · doi:10.1080/03081089608818448
[14] DOI: 10.1137/S0895479896298713 · Zbl 0889.15004 · doi:10.1137/S0895479896298713
[15] Mehta M. L., Matrix theory: Selected topics and useful results (1989)
[16] DOI: 10.1080/03081088708817827 · doi:10.1080/03081088708817827
[17] DOI: 10.1016/0024-3795(94)90486-3 · Zbl 0802.05053 · doi:10.1016/0024-3795(94)90486-3
[18] Minc H., Nonnegative matrices (1987)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.