A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees |
| |
Authors: | Yoshimi Egawa Kenta Ozeki |
| |
Institution: | 1. Department of Mathematical Information Science, Tokyo University of Science, Shinjuku-ku, Tokyo, 162-8601, Japan 2. National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan 3. JST, ERATO, Kawarabayashi Large Graph Project, Tokyo, Japan
|
| |
Abstract: | Let G be a connected simple graph, let X?V (G) and let f be a mapping from X to the set of integers. When X is an independent set, Frank and Gyárfás, and independently, Kaneko and Yoshimoto gave a necessary and sufficient condition for the existence of spanning tree T in G such that d T (x) for all x ∈ X, where d T (x) is the degree of x and T. In this paper, we extend this result to the case where the subgraph induced by X has no induced path of order four, and prove that there exists a spanning tree T in G such that d T (x) ≥ f(x) for all x ∈ X if and only if for any nonempty subset S ? X, |N G (S) ? S| ? f(S) + 2|S| ? ω G (S) ≥, where ω G (S) is the number of components of the subgraph induced by S. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|