Binding Number, Minimum Degree for Connected \((g, f+I)\)-factors in Graphs

Hengxia Liu1, Guizhen Liu2
1School of Mathematics and Informational Science, Yantai University Yantai, Shandong 264005, P. R. China
2School of Mathematics, Shandong University Jinan, Shandong 250100, P, R. China

Abstract

Let \( G \) be a graph of order \( n \). The \emph{binding number} of \( G \) is defined as

\[
\text{bind}(G) := \min \left\{ \frac{|N_G(X)|}{|X|} \mid \emptyset \neq X \subseteq V(G) \text{ and } N_G(X) \neq V(G) \right\}.
\]

A \((g, f)\)-factor is called a connected \((g, f)\)-factor if it is connected. A \((g, f)\)-factor \( F \) is called a Hamilton \((g, f)\)-factor if \( F \) contains a Hamilton cycle. In this paper, several sufficient conditions related to binding number and minimum degree for graphs to have connected \((g, f+1)\)-factors or Hamilton \((g, f)\)-factors are given.

Keywords: graph, (¢, f)-factor, connected factor, neighbor set Mathematics Subject Classification 2000: 05C70