ArticleOriginal scientific text
Title
Spanning caterpillars with bounded diameter
Authors 1, 2, 3, 4
Affiliations
- Memphis State University, Memphis, TN 38152, U.S.A.
- Emory University, Atlanta, GA 30322, U.S.A.
- University of Louisville, Louisville, KY 40292, U.S.A.
- 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 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 (at most n).
Keywords
distance, spaning tree
Bibliography
- A. Bialostocki, P. Dierker and B. Voxman, On monochromatic spanning trees of the complete graph, Preprint.
- S. Burr, Either a graph or its complement contains a spanning broom, Preprint.
- 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.