DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 15(2) (1995) 111-118
DOI: 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 cn3/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.