Spanning caterpillars with bounded diameter

• Autorzy: Ralph Faudree , Ronald Gould , Michael Jacobson , Linda Lesniak
• Języki publikacji: EN

Abstrakty

EN

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 $cn^{3/4}$ (at most n).

Słowa kluczowe

EN

distance; spaning tree

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C05: Trees

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1995
• Tom: 15
• Numer: 2
• Strony: 111-118

Daty

wydano

1995

otrzymano

1994-04-06

Twórcy

autor

Ralph Faudree

• Memphis State University, Memphis, TN 38152, U.S.A.

autor

Ronald Gould

• Emory University, Atlanta, GA 30322, U.S.A.

autor

Michael Jacobson

• University of Louisville, Louisville, KY 40292, U.S.A.

autor

Linda Lesniak

• Drew University, Madison, NJ 07940, U.S.A.

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1011