| Title:
|
On a characterization of $k$-trees (English) |
| Author:
|
Zeng, De-Yan |
| Author:
|
Yin, Jian-Hua |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
65 |
| Issue:
|
2 |
| Year:
|
2015 |
| Pages:
|
361-365 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
characterization |
| Keyword:
|
$k$-tree |
| Keyword:
|
$K_t$-minor |
| MSC:
|
05C05 |
| idZBL:
|
Zbl 06486951 |
| idMR:
|
MR3360431 |
| DOI:
|
10.1007/s10587-015-0180-7 |
| . |
| Date available:
|
2015-06-16T17:41:34Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144274 |
| . |
| Reference:
|
[1] Bodlaender, H. L.: A partial $k$-arboretum of graphs with bounded treewidth.Theor. Comput. Sci. 209 (1998), 1-45. Zbl 0912.68148, MR 1647486, 10.1016/S0304-3975(97)00228-4 |
| Reference:
|
[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. Zbl 1167.05308, MR 2419516, 10.1002/jgt.20302 |
| Reference:
|
[3] Cai, L.: On spanning 2-trees in a graph.Discrete Appl. Math. 74 (1997), 203-216. Zbl 0883.05040, MR 1444941, 10.1016/S0166-218X(96)00045-5 |
| Reference:
|
[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 |
| . |
