ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

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

Discussiones Mathematicae Graph Theory


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


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.


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.


[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.