Czasopismo
Tytuł artykułu
Treść / Zawartość
Pełne teksty:
Warianty tytułu
Języki publikacji
Abstrakty
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
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
111-118
Opis fizyczny
Daty
wydano
1995
otrzymano
1994-04-06
Twórcy
autor
- Memphis State University, Memphis, TN 38152, U.S.A.
autor
- Emory University, Atlanta, GA 30322, U.S.A.
autor
- University of Louisville, Louisville, KY 40292, U.S.A.
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1011