Premium
Spanning trees with leaf distance at least four
Author(s) -
Kaneko Atsushi,
Kano M.,
Suzuki Kazuhiro
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20221
Subject(s) - mathematics , combinatorics , spanning tree , minimum degree spanning tree , graph , connectivity , trémaux tree , shortest path tree , order (exchange) , discrete mathematics , line graph , pathwidth , finance , economics
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