# Spanning caterpillars with bounded diameter

Ralph Faudree; Ronald Gould; Michael Jacobson; Linda Lesniak

Discussiones Mathematicae Graph Theory (1995)

- Volume: 15, Issue: 2, page 111-118
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topRalph 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 -

## References

top- [1] A. Bialostocki, P. Dierker and B. Voxman, On monochromatic spanning trees of the complete graph, Preprint. Zbl0769.52014
- [2] S. Burr, Either a graph or its complement contains a spanning broom, Preprint.
- [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. Zbl0708.05057

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.