Discussiones Mathematicae Graph Theory 31(1) (2011) 143-159
doi: 10.7151/dmgt.1534

[BIBTex] [PDF] [PS]

CLOSURE FOR SPANNING TREES AND DISTANT AREA

Jun Fujisawa

Department of Applied Science
Kochi University
2-5-1 Akebono-cho, Kochi 780-8520, Japan
e-mail: fujisawa@is.kochi-u.ac.jp

Akira Saito

Department of Computer Science
Nihon University
Sakurajosui 3-25-40, Setagaya-Ku, Tokyo 156-8550, Japan
e-mail: asaito@chs.nihon-u.ac.jp

Ingo Schiermeyer

Institut für Diskrete Mathematik und Algebra
Technische Universität
Bergakademie Freiberg, D-09596 Freiberg, Germany
e-mail: schierme@mailserver.tu-freiberg.de

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 degG u+degG 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 degG u+degG v and the structure of the distant area for u and v. We prove that if the distant area contains Kr, we can relax the lower bound of degG u+degG 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.

2010 Mathematics Subject Classification: 05C05, 05C45.

References

[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:4<227::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.

Received 29 September 2009
Accepted 19 April 2010