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 (at most n).
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1011,
author = {Ralph Faudree and Ronald Gould and Michael Jacobson and Linda Lesniak},
title = {Spanning caterpillars with bounded diameter},
journal = {Discussiones Mathematicae Graph Theory},
volume = {15},
year = {1995},
pages = {111-118},
zbl = {0845.05030},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1011}
}
Ralph Faudree; Ronald Gould; Michael Jacobson; Linda Lesniak. Spanning caterpillars with bounded diameter. Discussiones Mathematicae Graph Theory, Tome 15 (1995) pp. 111-118. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1011/
[000] [1] A. Bialostocki, P. Dierker and B. Voxman, On monochromatic spanning trees of the complete graph, Preprint. | Zbl 0769.52014
[001] [2] S. Burr, Either a graph or its complement contains a spanning broom, Preprint.
[002] [3] P. Erdős, R. Faudree, A. Gyárfás, R. Schelp, Domination in colored complete graphs, J. Graph Theory 13 (1989) 713-718, doi: 10.1002/jgt.3190130607. | Zbl 0708.05057