Characterization of 1-Tough Graphs using Factors

Abstract

For a graph $G$, let $odd(G)$ and $\omega (G)$ denote the number of odd components and the number of components of $G$, respectively. Then it is well-known that $G$ has a 1-factor if and only if $odd(G-S)\le |S|$ for all $S\subset V(G)$. Also it is clear that $odd(G-S)\le \omega (G-S)$. In this paper we characterize a 1-tough graph $G$, which satisfies $\omega (G-S)\le |S|$ for all $\varnothing \ne S\subset V(G)$, using an $H$-factor of a set-valued function $H:V(G)\to \{\{1\},\{0,2\}\}$. Moreover, we generalize this characterization to a graph that satisfies $\omega (G-S)\le f(S)$ for all $\varnothing \ne S\subset V(G)$, where $f:V(G)\to \{1,3,5,\dots \}$.

References in corpus (1)

• An Extension of Cui-Kano's Characterization Problem on Graph Factors

Cited by in corpus (1)

• The Complexity of All $(g,f)$-Factor Problem