Geodesic
Closure for spanning trees and distant area
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 1, pp. 143-159

Voir la notice de l'article provenant de la source Library of Science

A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with deg_G u + deg_G v ≥ n-1, G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on deg_G u + deg_G v and the structure of the distant area for u and v. We prove that if the distant area contains K_r, we can relax the lower bound of deg_G u + deg_G v from n-1 to n-r. And if the distant area itself is a complete graph and G is 2-connected, we can entirely remove the degree sum condition.
Keywords: spanning tree, k-ended tree, closure 
@article{DMGT_2011_31_1_a7,
     author = {Fujisawa, Jun and Saito, Akira and Schiermeyer, Ingo},
     title = {Closure for spanning trees and distant area},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {143--159},
     publisher = {mathdoc},
     volume = {31},
     number = {1},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a7/}
}
TY  - JOUR
AU  - Fujisawa, Jun
AU  - Saito, Akira
AU  - Schiermeyer, Ingo
TI  - Closure for spanning trees and distant area
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 143
EP  - 159
VL  - 31
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a7/
LA  - en
ID  - DMGT_2011_31_1_a7
ER  - 
%0 Journal Article
%A Fujisawa, Jun
%A Saito, Akira
%A Schiermeyer, Ingo
%T Closure for spanning trees and distant area
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 143-159
%V 31
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a7/
%G en
%F DMGT_2011_31_1_a7
Fujisawa, Jun; Saito, Akira; Schiermeyer, Ingo. Closure for spanning trees and distant area. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 1, pp. 143-159. http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a7/