Isolated Toughness and Existence of \([a, b]\)-Factors in Graphs

Yinghong Ma1, Qinglin Yu2
1Department of Computing Science Shandong Normal University, Jinan, Shandong, China
2Center for Combinatorics, LPMC Nankai University, Tianjing, China 3Department of Mathematics and Statistics Thompson Rivers University, Kamloops, BC, Canada

Abstract

For a graph \( G \) with vertex set \( V(G) \) and edge set \( E(G) \), let \( i(G) \) be the number of isolated vertices in \( G \). The \emph{isolated toughness} of \( G \) is defined as

\[
I(G) = \min\left\{\frac{|S|}{i(G-S)} \mid S \subseteq V(G), i(G-S) \geq 2 \right\},
\]

if \( G \) is not complete; and \( I(K_n) = n-1 \). In this paper, we investigate the existence of \([a, b]\)-factors in terms of this graph invariant. We proved that if \( G \) is a graph with \( \delta(G) \geq a \) and \( I(G) \geq a \), then \( G \) has a fractional \( a \)-factor. Moreover, if \( \delta(G) \geq a \), \( I(G) > (a-1) + \frac{a-1}{b} \), and \( G-S \) has no \( (a-1) \)-regular component for any subset \( S \) of \( V(G) \), then \( G \) has an \([a, b]\)-factor. The latter result is a generalization of Katerinis’ well-known theorem about \([a, b]\)-factors (P. Katerinis, Toughness of graphs and the existence of factors, \emph{Discrete Math}. 80(1990), 81-92).