|
|||||
|
|
On a Spanning Tree with Specified Leaves |
|
| Authors: | Yoshimi?Egawa |
| Institution: | (1) Department of Mathematical Information Science, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162–8601, Japan;(2) The Research Institute of Educational Development, Tokai University, 2-28-4 Tomigaya, Shibuya-ku, Tokyo 151–8677, Japan;(3) Department of Mathematics, Asahi University, Hozumi, Gifu 223–8522, Japan;(4) Department of Mathematics, College of Science and Technology, Nihon University, 1-8 Kanda-Surugadai, Chiyoda-ku, Tokyo 101–8303, Japan |
| Abstract: | Let k ≥ 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least |G| + 1, then for each subset S of V(G) with |S| = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore’s theorem which guarantees the existence of a Hamilton path connecting any two vertices. Dedicated to Professor Hikoe Enomoto on his 60th birthday. |
| Keywords: | Spanning tree Leaf-connected Hamilton path Hamilton-connected |
| 本文献已被 SpringerLink 等数据库收录！ | |