NOTE Spectral Characterization of Tree-Width-Two Graphs |
| |
| Authors: | Andrei Kotlov |
| |
| Affiliation: | (1) Dept. of Combinatorics and Optimization, University of Waterloo; Waterloo, Ontario, Canada, N2L 3G1 and CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands; E-mail: andrei@cwi.nl, CA |
| |
| Abstract: | ) of a graph G, similar in spirit to his now-classical invariant . He showed that is minor-monotone and is related to the tree-width la(G) of G: and, moreover, , i.e. G is a forest. We show that and give the corresponding forbidden-minor and ear-decomposition characterizations. Received October 9, 1997/Revised July 27, 1999 |
| |
| Keywords: | AMS Subject Classification (1991) Classes: 05 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
