Characteristic vertices of trees*

Publisher Website
Google Scholar
Abstract
LetG=(V,E) be a graph with vertex set V={v 1,v 2,…vn } and edge set E. Denote by L(G) the n-by-n-matrix (aij ), where aij is the degree of vertex iwhen j=i; aij =−1 when j≠i and {i,j}∈E; and aij =0, otherwise. While L(G) depends on the labeling of V, its characteristic polynomialqG (x) does not. The main result of the first section is a family of inequalities between the coefficients of qG (x) and the coefficients of the chromatic polynomial of G. If λ n ⩾λ n−1⩾⋯⩾λ1 are the eigenvalues of L(G), then λ1=0 and λ2>0 if and only if G is connected. For connected graphs, the eigenvectors of L(G) corresponding to λ2 afford "characteristic valuations" of G, a concept introduced by M. Fiedler. Sections II and III explore the "characteristic vertices" arising from characteristic valuations when G is a tree.

This publication has 11 references indexed in Scilit: