A Spanning Tree with High Degree Vertices

摘要

Let G be a connected graph, let 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 , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all . 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 , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all .