Independence trees and Hamilton cycles
✍ Scribed by Broersma, Hajo; Tuinstra, Hilde
- Book ID
- 101228128
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 268 KB
- Volume
- 29
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Let G be a connected graph on n vertices. A spanning tree T of G is called an independence tree, if the set of end vertices of T (vertices with degree one in T ) is an independent set in G. If G has an independence tree, then α t (G) denotes the maximum number of end vertices of an independence tree of G. We show that determining α t of a graph is an NP-hard problem. We give the following analogue of a well-known result due to Chvátal and Erdös. If α t (G) ≤ κ(G) -1, then G is hamiltonian. We show that the condition is sharp. An I ≤k -tree of G is an independence tree of G with at most k end vertices or a Hamilton cycle of G. We prove the following two generalizations of a theorem of Ore. If G has an independence tree T with k end vertices such that two end vertices of T have degree sum at least n -k + 2 in G, then G has an I ≤k-1 -tree. If the degree sum of each pair of nonadjacent vertices of G is at least n -k + 1, then G has an I ≤k -tree. Finally, we prove the following analogue of a closure theorem due to Bondy and Chvátal. If the degree sum of two nonadjacent vertices u and v of G is at least n -1, then G has an I ≤k -tree if and only if G + uv has an I ≤k -tree (k ≥ 2). The last three results are all best possible with respect to the degree sum conditions.
📜 SIMILAR VOLUMES
## Abstract Let __G__ be a graph on __n__ vertices and __N__~2~(__G__) denote the minimum size of __N__(__u__) ∪ __N__(__v__) taken over all pairs of independent vertices __u, v__ of __G__. We show that if __G__ is 3‐connected and __N__~2~(__G__) ⩾ ½(__n__ + 1), then __G__ has a Hamilton cycle. We
## Abstract In this article, we consider the Hamilton‐Waterloo problem for the case of Hamilton cycles and triangle‐factors when the order of the complete graph __K__~__n__~ is even. We completely solved the problem for the case __n__≡24 (mod 36). For the cases __n__≡0 (mod 18) and __n__≡6 (mod 36)