On a characterization of -trees
Czechoslovak Mathematical Journal (2015)
- Volume: 65, Issue: 2, page 361-365
- ISSN: 0011-4642
Access Full Article
topAbstract
topHow to cite
topZeng, 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 -
References
top- Bodlaender, H. L., 10.1016/S0304-3975(97)00228-4, Theor. Comput. Sci. 209 (1998), 1-45. (1998) Zbl0912.68148MR1647486DOI10.1016/S0304-3975(97)00228-4
- Bose, P., Dujmović, V., Krizanc, D., Langerman, S., Morin, P., Wood, D. R., Wuhrer, S., 10.1002/jgt.20302, J. Graph Theory 58 (2008), 191-209. (2008) Zbl1167.05308MR2419516DOI10.1002/jgt.20302
- Cai, L., 10.1016/S0166-218X(96)00045-5, Discrete Appl. Math. 74 (1997), 203-216. (1997) Zbl0883.05040MR1444941DOI10.1016/S0166-218X(96)00045-5
- 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). (2003) MR1952980
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.