Characteristic vertices of trees. (English) Zbl 0636.05021

Merris, Russell

Linear Multilinear Algebra 22, No. 2, 115-131 (1987).

Let \(G=(V,E)\) be a graph with vertex set \(V=\{v_ 1,v_ 2,...,v_ n\}\) and edge set E. Denote by L(G) the n-by-n-matrix \((a_{ij})\), where \(a_{ij}\) is the degree of vertex i when \(j=i\); \(a_{ij}=-1\) when \(j\neq i\) and \(\{\) i,j\(\}\in E\); and \(a_{ij}=0\), otherwise. While L(G) depends on the labeling of V, its characteristic polynomial \(q_ G(x)\) does not. The main result of the first section is a family of inequalities between the coefficients of \(q_ G(x)\) and the coefficients of the chromatic polynomial of G. If \(\lambda_ n\geq \lambda_{n-1}\geq...\geq \lambda_ 1\) are the eigenvalues of L(G), then \(\lambda_ 1=0\) and \(\lambda_ 2>0\) if and only if G is connected. For connected graphs, the eigenvectors of L(G) corresponding to \(\lambda_ 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.

MSC:

05C05	Trees
05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)

Keywords:

matrix; characteristic polynomial; chromatic polynomial; characteristic valuations; characteristic vertices

References:

[1]	Biggs N., Algebraic Graph Theory (1974) · Zbl 0797.05032
[2]	DOI: 10.1016/0012-365X(83)90034-1 · Zbl 0527.05050
[3]	DOI: 10.1080/03081088508817683 · Zbl 0615.05039
[4]	Cvetković D., Spectra of Graphs (1979)
[5]	DOI: 10.1016/0024-3795(85)90281-2 · Zbl 0559.05041
[6]	Fiedler M., Czech. Math. J. 23 pp 298– (1973)
[7]	Fiedler M., Czech. Math. J. 25 pp 607– (1975)
[8]	Fiedler M., Czech. Math. J. 25 pp 619– (1975)
[9]	Marshall A. W., Inequalities: Theory of Majorization and Its Applications (1979) · Zbl 0437.26007
[10]	DOI: 10.1137/0607056 · Zbl 0605.05009
[11]	DOI: 10.1016/S0021-9800(68)80087-0 · Zbl 0173.26203
[12]	Rebman K. R., Lecture Notes
[13]	DOI: 10.1016/0012-365X(73)90108-8 · Zbl 0258.05113
[14]	DOI: 10.1090/S0002-9904-1932-05460-X · Zbl 0005.14602
[15]	Wilf H. S., Which Polynomials are Chromatic (1973) · Zbl 0352.05031
[16]	Wilf H. S., Which Polynomials are Chromatic (1976) · Zbl 0352.05031
[17]	Grone R., Czech. Math. J. (1976)