DMGT

PDF

Discussiones Mathematicae Graph Theory 15(2) (1995) 111-118
DOI: https://doi.org/10.7151/dmgt.1011

SPANNING CATERPILLARS WITH BOUNDED DIAMETER

Ralph Faudree

Memphis State University
Memphis, TN 38152, U.S.A.

Ronald Gould

Emory University
Atlanta, GA 30322, U.S.A.

Michael Jacobson

University of Louisville
Louisville, KY 40292, U.S.A.

Linda Lesniak

Drew University
Madison, NJ 07940, U.S.A.

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 complement G has a spanning caterpillar of diameter at most 2logn. 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).

Keywords: distance, spaning tree.

1991 Mathematics Subject Classification: 05C05, 05C12.

References

[1]	A. Bialostocki, P. Dierker and B. Voxman, On monochromatic spanning trees of the complete graph, Preprint.
[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.