On a k-Tree Containing Specified Leaves in a Graph |
| |
Authors: | Haruhide Matsuda Hajime Matsumura |
| |
Institution: | (1) Department of General Education, Kyushu Tokai University, Minami-Aso, Aso, Kumamoto 869-1404, Japan;(2) Department of Mathematics, Keio University, Hiyoshi, Kohoku-ku, Yokohama 223-8522, Japan |
| |
Abstract: | A k-tree of a graph is a spanning tree with maximum degree at most k. We give sufficient conditions for a graph G to have a k-tree with specified leaves: Let k,s, and n be integers such that k≥2, 0≤s≤k, and n≥s+1. Suppose that (1) G is (s+1)-connected and the degree sum of any k independent vertices of G is at least |G|+(k−1)s−1, or (2) G is n-connected and the independence number of G is at most (n−s)(k−1)+1. Then for any s specified vertices of G, G has a k-tree containing them as leaves. We also discuss the sharpness of the results.
This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement
of Young Scientists, 15740077, 2005
This research was partially supported by the Japan Society for the Promotion of Science for Young Scientists. |
| |
Keywords: | Tree Spanning subgraph Ore Independence number Factor |
本文献已被 SpringerLink 等数据库收录! |
|