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

Abstract

top
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 d e g G u + d e g 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 d e g G u + d e g 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 d e g G u + d e g 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.

How to cite

top

Jun 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. [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. [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. [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. [4] G. Chartrand and L. Lesniak, Graphs & Digraphs (4th ed.), (Chapman and Hall/CRC, Boca Raton, Florida, U.S.A. 2005). 
  5. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.