A Spanning Tree with High Degree Vertices |
| |
Authors: | Kenta Ozeki Tomoki Yamashita |
| |
Institution: | 1. Department of Mathematics, Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama, 223-0061, Japan 2. College of Liberal Arts and Sciences, Kitasato University, 1-15-1 Kitasato, Sagamihara, 228-8555, Japan
|
| |
Abstract: | Let G be a connected graph, let ${X \subset V(G)}$ and let f be a mapping from X to {2, 3, . . .}. Kaneko and Yoshimoto (Inf Process Lett 73:163–165, 2000) conjectured that if |N G (S) ? X| ≥ f (S) ? 2|S| + ω G (S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d T (x) ≥ f (x) for all ${x \in X}$ . In this paper, we show a result with a stronger assumption than this conjecture; if |N G (S) ? X| ≥ f (S) ? 2|S| + α(S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d T (x) ≥ f (x) for all ${x \in X}$ . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|