Geodesic
On a characterization of $k$-trees
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 2, pp. 361-365 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-015-0180-7
Classification : 05C05
Keywords: characterization; $k$-tree; $K_t$-minor 
@article{10_1007_s10587_015_0180_7,
     author = {Zeng, De-Yan and Yin, Jian-Hua},
     title = {On a characterization of $k$-trees},
     journal = {Czechoslovak Mathematical Journal},
     pages = {361--365},
     year = {2015},
     volume = {65},
     number = {2},
     doi = {10.1007/s10587-015-0180-7},
     mrnumber = {3360431},
     zbl = {06486951},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0180-7/}
}
TY  - JOUR
AU  - Zeng, De-Yan
AU  - Yin, Jian-Hua
TI  - On a characterization of $k$-trees
JO  - Czechoslovak Mathematical Journal
PY  - 2015
SP  - 361
EP  - 365
VL  - 65
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0180-7/
DO  - 10.1007/s10587-015-0180-7
LA  - en
ID  - 10_1007_s10587_015_0180_7
ER  - 
%0 Journal Article
%A Zeng, De-Yan
%A Yin, Jian-Hua
%T On a characterization of $k$-trees
%J Czechoslovak Mathematical Journal
%D 2015
%P 361-365
%V 65
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0180-7/
%R 10.1007/s10587-015-0180-7
%G en
%F 10_1007_s10587_015_0180_7
Zeng, De-Yan; Yin, Jian-Hua. On a characterization of $k$-trees. Czechoslovak Mathematical Journal, Tome 65 (2015) no. 2, pp. 361-365. doi: 10.1007/s10587-015-0180-7

[1] Bodlaender, H. L.: A partial $k$-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209 (1998), 1-45. | DOI | MR | Zbl

[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 | MR | Zbl

[3] Cai, L.: On spanning 2-trees in a graph. Discrete Appl. Math. 74 (1997), 203-216. | DOI | MR | Zbl

[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

Cité par Sources :