Some results on spanning trees |
| |
| Authors: | Bing Yao Zhong-fu Zhang Jian-fang Wang |
| |
| Institution: | 1. College of Mathematics and Information Science, Northwest Normal University, Lanzhou, 730070, China
2. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, China
|
| |
| Abstract: | Some structures of spanning trees with many or less leaves in a connected graph are determined. We show (1) a connected graph
G has a spanning tree T with minimum leaves such that T contains a longest path, and (2) a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ(G) = Δ(T) and the number of leaves of T is not greater than n − D(G) + 1, where D(G) is the diameter of G. |
| |
| Keywords: | Spanning tree leaves diameter Steiner tree independent number |
| 本文献已被 维普 SpringerLink 等数据库收录！ |
|
