# Closure for spanning trees and distant area

Jun Fujisawa; Akira Saito; Ingo Schiermeyer

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 1, page 143-159
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJun Fujisawa, Akira Saito, and Ingo Schiermeyer. "Closure for spanning trees and distant area." Discussiones Mathematicae Graph Theory 31.1 (2011): 143-159. <http://eudml.org/doc/271024>.

@article{JunFujisawa2011,

abstract = {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.},

author = {Jun Fujisawa, Akira Saito, Ingo Schiermeyer},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {spanning tree; k-ended tree; closure; -ended tree, closure},

language = {eng},

number = {1},

pages = {143-159},

title = {Closure for spanning trees and distant area},

url = {http://eudml.org/doc/271024},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Jun Fujisawa

AU - Akira Saito

AU - Ingo Schiermeyer

TI - Closure for spanning trees and distant area

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 1

SP - 143

EP - 159

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

LA - eng

KW - spanning tree; k-ended tree; closure; -ended tree, closure

UR - http://eudml.org/doc/271024

ER -

## References

top- [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. Zbl0331.05138
- [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. Zbl0789.05059
- [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 Zbl0919.05017
- [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. Zbl0746.05041

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.