Toughness and the existence of Hamiltonian [a,b]-factors of graphs
Abstract
The toughness of a graph G,denoted by t(G),is defined as t(G)= min{|S|/w(G-S): S ⊆ V(G),w(G-S)≥2} where w(G - S)denotes the number of components of G-S or t(G)= +∞ if G is a complete graph. Let a and b be nonnegative integers with 2 ≤ a ≤ b - 1, and let G be a Hamiltonian graph of order n with n ≥ a +2. An [a,b]-factor F of G is called a Hamiltonian [a,b]-factor if F contains a Hamiltonian cycle. In this paper,it is proved that G has a Hamiltonian [a,a + l]-factor if t(G)> a and has a Hamiltonian [a,b]-factor if t(G)≥ a - 1 + a-1/b-2.This result is an improvement and extension of H. Enomoto and P. Katerinis's results(H. Enomoto,B. Jackson,P. Katerinis,A. Satio,Toughness and the existence of k-factors,Journal of Graph Theory 9(1985),87-95; P. Katerinis,Toughness of graphs and the existence of factors,Discrete Mathematics 80(1990),81-92).
