Spanning trees with leaf distance at least four |
| |
Authors: | Atsushi Kaneko M Kano Kazuhiro Suzuki |
| |
Institution: | Department of Computer and Information Sciences, Faculty of Engineering, Ibaraki University, Hitachi, Ibaraki 316‐8511, Japan |
| |
Abstract: | For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007 |
| |
Keywords: | spanning tree leaf leaf distance |
|
|