PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1995 | 15 | 2 | 111-118
Tytuł artykułu

Spanning caterpillars with bounded diameter

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
15
Numer
2
Strony
111-118
Opis fizyczny
Daty
wydano
1995
otrzymano
1994-04-06
Twórcy
  • Memphis State University, Memphis, TN 38152, U.S.A.
autor
  • 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.
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
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.