Spectral characterization of tree-width-two graphs

Authors
Citation
A. Kotlov, Spectral characterization of tree-width-two graphs, COMBINATORI, 20(1), 2000, pp. 147-152
Citations number
4
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683 → ACNP
Volume
20
Issue
1
Year of publication
2000
Pages
147 - 152
Database
ISI
SICI code
0209-9683(2000)20:1<147:SCOTG>2.0.ZU;2-I
Abstract
In his recent preprint "Multiplicities of eigenvalues and tree-width of gra phs," Colin de Verdiere introduced a new spectral invariant (denoted here b y l(G)) of a graph G, similar in spirit to his now-classical invariant mu(G ). He showed that l(G) is minor-monotone and is related to the tree-width l a(G) of G: l(G)less than or equal to la(G) and, moreover, l(G)less than or equal to 1 <-> la(G)=1, i.e. G is a forest. We show that l(G) = 2 <-> la(G) = 2 and give the corresponding forbidden-minor and ear-decomposition chara cterizations.