Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
characterization; $k$-tree; $K_t$-minor
characterization; $k$-tree; $K_t$-minor
Summary:
A graph $G$ is a $k$-tree if either $G$ is the complete graph on $k+1$ vertices, or $G$ has a vertex $v$ whose neighborhood is a clique of order $k$ and the graph obtained by removing $v$ from $G$ is also a $k$-tree. Clearly, a $k$-tree has at least $k+1$ vertices, and $G$ is a 1-tree (usual tree) if and only if it is a $1$-connected graph and has no $K_3$-minor. In this paper, motivated by some properties of 2-trees, we obtain a characterization of $k$-trees as follows: if $G$ is a graph with at least $k+1$ vertices, then $G$ is a $k$-tree if and only if $G$ has no $K_{k+2}$-minor, $G$ does not contain any chordless cycle of length at least 4 and $G$ is $k$-connected.
References:
[1] Bodlaender, H. L.: A partial $k$-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209 (1998), 1-45. DOI 10.1016/S0304-3975(97)00228-4 | MR 1647486 | Zbl 0912.68148
[2] Bose, P., Dujmović, V., Krizanc, D., Langerman, S., Morin, P., Wood, D. R., Wuhrer, S.: A characterization of the degree sequences of 2-trees. J. Graph Theory 58 (2008), 191-209. DOI 10.1002/jgt.20302 | MR 2419516 | Zbl 1167.05308
[3] Cai, L.: On spanning 2-trees in a graph. Discrete Appl. Math. 74 (1997), 203-216. DOI 10.1016/S0166-218X(96)00045-5 | MR 1444941 | Zbl 0883.05040
[4] Reed, B. A.: Algorithmic aspects of treewidth. Recent Advances in Algorithms and Combinatorics CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Vol. 11 Springer, New York 85-107 (2003). MR 1952980
Search
Partner of
