Geodesic
Spanning caterpillars with bounded diameter
Discussiones Mathematicae. Graph Theory, Tome 15 (1995) no. 2, pp. 111-118 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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).
Keywords: distance, spaning tree 
@article{DMGT_1995_15_2_a0,
     author = {Faudree, Ralph and Gould, Ronald and Jacobson, Michael and Lesniak, Linda},
     title = {Spanning caterpillars with bounded diameter},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {111--118},
     year = {1995},
     volume = {15},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a0/}
}
TY  - JOUR
AU  - Faudree, Ralph
AU  - Gould, Ronald
AU  - Jacobson, Michael
AU  - Lesniak, Linda
TI  - Spanning caterpillars with bounded diameter
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1995
SP  - 111
EP  - 118
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a0/
LA  - en
ID  - DMGT_1995_15_2_a0
ER  - 
%0 Journal Article
%A Faudree, Ralph
%A Gould, Ronald
%A Jacobson, Michael
%A Lesniak, Linda
%T Spanning caterpillars with bounded diameter
%J Discussiones Mathematicae. Graph Theory
%D 1995
%P 111-118
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a0/
%G en
%F DMGT_1995_15_2_a0
Faudree, Ralph; Gould, Ronald; Jacobson, Michael; Lesniak, Linda. Spanning caterpillars with bounded diameter. Discussiones Mathematicae. Graph Theory, Tome 15 (1995) no. 2, pp. 111-118. http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a0/

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