On a characterization of $k$-trees

Zeng, De-Yan, and Yin, Jian Hua. "On a characterization of $k$-trees." Czechoslovak Mathematical Journal 65.2 (2015): 361-365. <http://eudml.org/doc/270105>.

@article{Zeng2015,
abstract = {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.},
author = {Zeng, De-Yan, Yin, Jian Hua},
journal = {Czechoslovak Mathematical Journal},
keywords = {characterization; $k$-tree; $K_t$-minor},
language = {eng},
number = {2},
pages = {361-365},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On a characterization of $k$-trees},
url = {http://eudml.org/doc/270105},
volume = {65},
year = {2015},
}

TY - JOUR
AU - Zeng, De-Yan
AU - Yin, Jian Hua
TI - On a characterization of $k$-trees
JO - Czechoslovak Mathematical Journal
PY - 2015
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 2
SP - 361
EP - 365
AB - 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.
LA - eng
KW - characterization; $k$-tree; $K_t$-minor
UR - http://eudml.org/doc/270105
ER -