A k-Tree Containing Specified Vertices |
| |
Authors: | Shuya Chiba Ryota Matsubara Kenta Ozeki Masao Tsugaki |
| |
Institution: | 1. Department of Mathematical Information Science, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo, 162-8601, Japan 2. Tokyo, Japan 3. Department of Mathematics, Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama, 223-0061, Japan
|
| |
Abstract: | A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let ${S \subseteq V(G)}A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let S í V(G){S \subseteq V(G)} with κ(S) ≥ 1. Suppose that for every l > κ(S), there exists an integer t such that
1 £ t £ (k-1)l+2 - ?\fracl-1k ?{1 \le t \leq (k-1)l+2 - \lfloor \frac{l-1}{k} \rfloor} and the degree sum of any t independent vertices of S is at least n + tl − kl − 1. Then G has a k-tree containing S. We also show some new results on a spanning k-tree as corollaries of the above theorem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|