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 , 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 and the structure of the distant area for u and v. We prove that if the distant area contains , we can relax the lower bound of 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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1534,
author = {Jun Fujisawa and Akira Saito and Ingo Schiermeyer},
title = {Closure for spanning trees and distant area},
journal = {Discussiones Mathematicae Graph Theory},
volume = {31},
year = {2011},
pages = {143-159},
zbl = {1284.05062},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1534}
}
Jun Fujisawa; Akira Saito; Ingo Schiermeyer. Closure for spanning trees and distant area. Discussiones Mathematicae Graph Theory, Tome 31 (2011) pp. 143-159. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1534/
[000] [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. | Zbl 0331.05138
[001] [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. | Zbl 0789.05059
[002] [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:4<227::AID-JGT2>3.0.CO;2-W | Zbl 0919.05017
[003] [4] G. Chartrand and L. Lesniak, Graphs & Digraphs (4th ed.), (Chapman and Hall/CRC, Boca Raton, Florida, U.S.A. 2005).
[004] [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. | Zbl 0746.05041