Degree Bounded Spanning Trees |
| |
Authors: | Jun Fujisawa Hajime Matsumura Tomoki Yamashita |
| |
Institution: | 1. Department of Applied Science, Kochi University, 2-5-1 Akebono-cho, Kochi, 780-8520, Japan 2. Kyoto, Japan 3. College of Liberal Arts and Sciences, Kitasato University, 1-15-1 Kitasato, Sagamihara, 228-8555, Japan
|
| |
Abstract: | In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?v ? V(T)max{dT(v)-k,0} £ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|