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/

[1] J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111-135, doi: 10.1016/0012-365X(76)90078-9.

[2] H.J. Broersma and I. Schiermeyer, A closure concept based on neighborhood unions of independent triples, Discrete Math. 124 (1994) 37-47, doi: 10.1016/0012-365X(92)00049-W.

[3] H. Broersma and H. Tuinstra, Independence trees and Hamilton cycles, J. Graph Theory 29 (1998) 227-237, doi: 10.1002/(SICI)1097-0118(199812)29:4227::AID-JGT2>3.0.CO;2-W

[4] G. Chartrand and L. Lesniak, Graphs Digraphs (4th ed.), (Chapman and Hall/CRC, Boca Raton, Florida, U.S.A. 2005).

[5] Y.J. Zhu, F. Tian and X.T. Deng, Further consideration on the Bondy-Chvátal closure theorems, in: Graph Theory, Combinatorics, Algorithms, and Applications (San Francisco, CA, 1989), 518-524.