Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646814 | Discrete Mathematics | 2016 | 5 Pages |
Abstract
We determine the relationship between the graph parameters neighbourhood-width and path-width of trees, that turn out equivalent. As our main combinatorial tool, we show that the neighbourhood-width of a tree T=(V,E)T=(V,E) is at least k+1k+1 if for some vertex v∈Vv∈V, forest T[V−{v}]T[V−{v}] has at least three non-edgeless components of neighbourhood-width at least kk.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Frank Gurski, Stefan Neidig, Eda Yilmaz,