Algebraic connectivity and the characteristic set of a graph

Bapat, R .B. ; Pati, Sukanta (1998) Algebraic connectivity and the characteristic set of a graph Linear and Multilinear Algebra, 45 (2-3). pp. 247-273. ISSN 0308-1087

Full text not available from this repository.

Official URL: http://www.informaworld.com/smpp/content~db=all~co...

Related URL: http://dx.doi.org/10.1080/03081089808818590

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.

Item Type:Article
Source:Copyright of this article belongs to Taylor and Francis Ltd.
Keywords:Laplacian Matrix; Characteristic Set; Algebraic Connectivity; Moore-Penrose Inverse
ID Code:1399
Deposited On:05 Oct 2010 12:50
Last Modified:13 May 2011 08:10

Repository Staff Only: item control page