Search

Start Over Coverage 361-365

2. On a characterization of k-trees

Creator:
Zeng, De-Yan and Yin, Jian-Hua
Format:
print, bez média, and svazek
Type:
model:article and TEXT
Subject:
matematika, mathematics, characterization, k-tree, K_{t} -minor, 13, and 51
Language:
English
Description:
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., De-Yan Zeng, Jian-Hua Yin., and Obsahuje seznam literatury
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public