Spanning caterpillars with bounded diameter

Ralph Faudree, et al. "Spanning caterpillars with bounded diameter." Discussiones Mathematicae Graph Theory 15.2 (1995): 111-118. <http://eudml.org/doc/270587>.

@article{RalphFaudree1995,
abstract = {A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most $cn^\{3/4\}$ (at most n).},
author = {Ralph Faudree, Ronald Gould, Michael Jacobson, Linda Lesniak},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distance; spaning tree; spanning tree; caterpillar; diameter},
language = {eng},
number = {2},
pages = {111-118},
title = {Spanning caterpillars with bounded diameter},
url = {http://eudml.org/doc/270587},
volume = {15},
year = {1995},
}

TY - JOUR
AU - Ralph Faudree
AU - Ronald Gould
AU - Michael Jacobson
AU - Linda Lesniak
TI - Spanning caterpillars with bounded diameter
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 2
SP - 111
EP - 118
AB - A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most $cn^{3/4}$ (at most n).
LA - eng
KW - distance; spaning tree; spanning tree; caterpillar; diameter
UR - http://eudml.org/doc/270587
ER -