|
|||||
|
|
Spanning Trees with Few Leaves |
|
| Authors: | Masao Tsugaki Tomoki Yamashita |
| Institution: | (1) Department of Mathematical Information Science, Science University of Tokyo, 1–3 Kagurazaka, Shinjuku-ku, Tokyo 162–8601, Japan;(2) Department of Mathematics School of Dentistry, Asahi University, 1851 Hozumi, Gifu 501–0296, Japan |
| Abstract: | In this paper, we prove that an m-connected graph G on n vertices has a spanning tree with at most k leaves (for k ≥ 2 and m ≥ 1) if every independent set of G with cardinality m + k contains at least one pair of vertices with degree sum at least n − k + 1. This is a common generalization of results due to Broersma and Tuinstra and to Win. |
| Keywords: | Degree sum condition spanning tree few leaves |
| 本文献已被 SpringerLink 等数据库收录！ | |