ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 15(2) (1995)
Memphis State University
Memphis, TN 38152, U.S.A.
Atlanta, GA 30322, U.S.A.
University of Louisville
Louisville, KY 40292, U.S.A.
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.