Algebraic connectivity and the characteristic set of a graph

Abstract

Let Gbe a connected weighted graph on vertices {1,2,...,n} and L be the Laplacian matrix of G Let µ be the second smallest eigenvalue of L and Y be an eigenvector corresponding to µ. A characteristic vertex is a vertex v such that Y(v) = 0 and Y(w) ≠ 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 characteristic vertices and the characteristic edges together form the characteristic 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. 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.