ArticleOriginal scientific text

Title

Spanning caterpillars with bounded diameter

Authors 1, 2, 3, 4

Affiliations

  1. Memphis State University, Memphis, TN 38152, U.S.A.
  2. Emory University, Atlanta, GA 30322, U.S.A.
  3. University of Louisville, Louisville, KY 40292, U.S.A.
  4. 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 cn34 (at most n).

Keywords

distance, spaning tree

Bibliography

  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.
Pages:
111-118
Main language of publication
English
Received
1994-04-06
Published
1995
Exact and natural sciences