In this paper, we consider (\(a,b\))- parity factors in graphs and obtain a toughness condition for the existence of (\(a,b\))-parity factors. Furthermore, we show that the result is sharp in some sense.
Let \(G\) be a simple connected graph with vertex set \(V(G)\) and edge set \(E(G)\). Given a vertex \(x\in V(G)\), let \(N_G(x)\) denote the set of vertices adjacent to \(x\) in \(G\) and \(d_G(x)=|N_G(x)|\). A subset \(I\) of \(V(G)\) is an independent set of \(G\) if no two elements of \(I\) are adjacent in \(G\) and a subset \(C\) of \(V(G)\) is a covering set if every edge of \(G\) has at least one end in \(C\). For other terminologies and notations, we refer the reader to [2].
Given two positive integer functions \(g,f\) with \(g(x)\equiv f(x)(\mod2)\), we say that \(G\) has a (\(g,f\))-parity factor if there is a spanning subgraph \(H\) of \(G\) such that \(g(x)\leq d_H(x)\leq f(x)\) and \(d_H(x)\equiv f(x)\mod(2)\)for every \(x\in V(G)\). Let \(a\leq b\) be two integers and \(a\equiv b(\mod 2)\). If \(g(x)=a\) and \(f(x)=b\) for all \(x\in V(G)\), then a (\(g,f\))-parity factor is called an (\(a,b\))-parity factor.
Lovász gave a characterization of graphs having (\(g,f\))-parity factors. Amahashi [1] obtained a condition for a graph to have (\(1,k\))-odd factors, which was generalized to (\(1,f\))-odd factors by Cui and Kano [7].
Theorem 1.1. A graph \(G\) has a (\(g,f\))-parity factor if and only if for any two disjoint subsets \(D,S\) of \(V(G)\), \[f(D)-g(S)+d_{G-D}(S)-q(D,S)\geq0,\] where \(q(D,S)\) denotes the number of components in \(G-D-S\), such that \(g(V(C))+e_G(V(C),S)\equiv1(\mod2)\), where the component \(C\) is called \(g\)-odd components.
Theorem 1.2. A graph \(G\) has a (\(1,k\))-odd factor if and only if for any subset of \(V(G)\), \[C_o(G-S)\leq k|S|,\] where \(C_o(G-S)\) denotes the number of odd components of \(G-S\).
Let \(G\) be a non-complete graph and \(t\) be a real number. We say \(G\) is \(t\)-tough, if \(|S|\geq t\omega(G-S)\), for any vertex-cutset \(S\) of \(G\), where \(\omega(G-S)>1\) is the number of components in \(G-S\). The largest \(t\) such that \(G\) is \(t\)-tough is called the toughness of \(G\) and is denoted by \(t(G)\). That is, \[t(G)=\min\left\{\frac{|S|}{\omega(G-S)}|S\subset V(G),\omega(G-S)\geq2\right\}.\]
If \(G\simeq K_n\), \(t(G)\) is defined as \(\infty\).
Chvátal introduced the concept of toughness in [3] and made the following conjecture.
Conjecture 1.3. Let \(G\) be a graph and \(k\) a positive integer such that \(k|V(G)|\) is even and \(G\) is \(k\)-tough. Then \(G\) has a \(k\)-factor.
In [4] it was proved that the conjecture is true. Katernis [5] presented two theorems which implied the truth of Chvátal’s conjecture.
Theorem 1.4. Let \(G\) be a graph and a,b two positive integers. Suppose that \[t(G)\ge \left\{ \begin{array}{cc} \frac{(b+a)^2+2(b-a)}{4a}, & \text{if}\ b\equiv a(\mod2),\\ \frac{(b+a)^2+2(b-a)+1}{4a}, & \text{otherwise}. \end{array} \right.\]
If \(f\) is a positive integer function such that \(f(V(G))\) is even and \(a\leq f(x)\leq b\) for all \(x\in V(G)\), then \(G\) has an \(f\)-factor.
Theorem 1.5. Let \(G\) be a graph and a,b two positive integers with \(b\geq a\). If \(t(G)\geq (a-1)+\frac{a}{b}\) and \(a|V(G)|\) is even when \(a=b\), then \(G\) has an (\(a,b\))-factor.
In [6], they obtained a degree condition for the existence of (\(a,b\))-parity factors in graphs. In this paper we give a sufficient condition for a graph to have an (\(a,b\))-parity factor in terms of toughness of \(G\). Our main result strengthens Katernis’s results in some sense.
Theorem 1.6. Let \(G\) be a connected graph. If \(b\) is an odd integer and \(|V(G)|\) is even, \(t(G)\geq \frac{1}{b}\), then \(G\) has a (\(1,b\))-odd factor.
Theorem 1.7. Let \(G\) be a connected graph, \(a\) and \(b\) two integers with \(b\geq a\geq2\) and \(a\equiv b(\mod2)\). Suppose that \(a|V(G)|\) is even and \(t(G)\geq a-1+\frac{a}{b}\), then \(G\) has an (\(a,b\))-parity factor.
For the proof of main theorem we need the following lemmas in [3] and [5] respectively.
Lemma 1.8. If a graph \(G\) is not complete, then \(t(G)\leq\frac{1}{2}\delta(G)\)
Lemma 1.9. Let \(H\) be a graph and \(S_1,…,S_{a-1}\) be a partion of the vertices of \(H\) such that if \(x\in S_j\) then \(D_H(x)\leq j\).(We allow \(S_j=\emptyset\).) Then there exists a covering set \(C\) of H and an independent set \(I\), such that \[\sum\limits_{j=1}^{a-1}(a-j)c_j\leq\sum\limits_{j=1}^{a-1}j(a-j)i_j,\]where \(|I\cap S_j|=i_j and |C\cap S_j|=c_j\), for every \(j=1,…,a-1\).
The result in Theorem 1.6 is sharp. We consider \(G_1=K_m\vee (mb+1)K_1\), where “\(\vee\)” means join and \(m\) is an arbitrary positive integer. It is easy to fnd out that \(t(G)=\frac{m}{mb+1}<\frac{1}{b}\) and \(b|S|<C_0(G-S)\) if \(S=V(K_m)\). By Theorem 1.2 \(G_1\) has no (\(1,b\))-odd factor.
The assumption \(|V(G)|\) even is necessary. For example, \(K_{1,2n}\) has no (\(1,b\))-odd factor.
To see the result in Theorem 1.7 is sharp even \(a\) is even. We construct the following graph \(G\): \(V(G)=A\cup B\cup C\) where \(A,B,C\) are disjoint with \(|A|=(nb+1)(a-1)\), \(|B|=nb+1\) and \(|C|=na\). \(A\) is isomorphic to \((nb+1)K_{a-1}\), and \(B=(nb+1)K_1\) , while \(C\) is a clique of \(G\). Other edges in \(G\) are all edges between every pair \(K_1\) of \(A\) and \(K_{a-1}\) of \(B\) respectively, and all the edges between \(B\) and \(C\). Let \(X=A\cup C\). Then \(|X|=(nb+1)(a-1)+na\) and \(\omega(G-X)=nb+1\). This follows that \[t(G)\leq\frac{|X|}{\omega(G-X)}=a-1+a\frac{n}{nb+1}<a-1+\frac{a}{b}.\]
If we set \(D=C\) and \(S=A\), \(b|D|-a|S|+d_{G-D}(S)-q(D,S)=-a\leq-2\), where \(q(D,S)=nb+1\). Clearly \(G\) has no (\(a,b\))-parity factor.
Proof. Suppose to the contary, \(G\) has no (\(1,b\))-factor. There exists a subset \(S\) of \(V(G)\) such that \(C_o(G-S)>b|S|\), where \(C_o(G-S)\) denoted the odd components of \(G-S\). Obviously \(S\neq \emptyset\). Since \(|V(G)|\) is even and \(S=\emptyset\), \(C_o(G-S)=C_o(G)=0>0\), a contradiction. Therefore \(t(G)\leq \frac{|S|}{\omega(G-S)}\leq\frac{|S|}{C_o(G-S)}<\frac{|S|}{b|S|}=\frac{1}{b},\) contradicts to the assumption. ◻
Proof. Suppose that \(G\) has no (\(a,b\))-parity factor, there exist two disjoint subsets \(D,S\subseteq V(G)\) such that
\[\label{eq1} b|D|-a|S|+d_{G-D}(S)-q(D,S)\leq-1. \tag{1}\]
Obviously \(D\cup S\neq\emptyset\). Otherwise \(q(D,S)=0\), since \(a|V(G)|\) is even. Thus \(0\leq -1\) a contradiction.
Clearly \(S\neq\emptyset\).
If \(S=\emptyset\), then \(q(D,\emptyset)\geq b|D|+1\geq2\). By the definition of \(t(G)\), we have \(t(G)\leq\frac{|D|}{\omega(G-D}\leq\frac{|D|}{b|D|+1}<\frac{1}{b},\) contradicts to \(t(G)\geq a-1+\frac{a}{b}\).
Let \(\Delta=\max\{d_{G-D}(x)|x\in S\}\) and \(S_j=\{x\in S|d_{G-D}(x)=j\}\), \(|S_j|=s_j\), \(0\leq j\leq\Delta\). Set \(H=G[S_1\cup S_2\cup…\cup S_{a-1}]\). Since for every \(x\in S_j\), \(d_H(x)\leq j\), by Lemma 9 we can find a covering set \(C'\) and an independent set \(I'\) of \(H\), such that\[\sum\limits_{j=1}^{a-1}(a-j)c_j'\leq\sum\limits_{j=1}^{a-1}j(a-j)i_j',\]where \(|I'\cap S_j|=i_j'\) and \(|C'\cap S_j|=c_j'\) for every \(j=1,2,…,a-1\). We may assume that \(I'\) is a maximal independent set of \(H\). We choose a maximal independent set \(I\) of \(G[S]-S_0\), such that \(I'\subseteq I\). Putting \(C=(S-S_0)\setminus I\) we have \(C'\subseteq C\), by the maximality of \(I'\). If we put \(I_j=I\cap S_j\), \(|I_j|=i_j\), \(C_j=C\cap S_j\) and \(|C_j|=c_j\), then for \(1\leq j\leq a-1\), \[i_j=i_j',\ c_j=c_j'.\]
Now Let \(\Omega\) be the set of components of \(W=G-D-S\) and set \(Y=\{H\in \Omega|e(x,I)=0,\ \text{for}\ x\in V(H)\}\), \(X_1=\{H\in \Omega|e(x,I)\geq2,\ \text{for}\ x\in V(H)\}\), \(X_2=\Omega\setminus(X_1\cup Y)\). Let \(y=|Y|\), \(x_1=|X_1|\) and \(x_2=|X_2|\). Suppose that \(X_2=\{H_1,…,H_{x_2}\}\) and choose \(z_i\in V(H_i)\) such that \(e(z_i,I)=1\) for every \(1\leq i\leq x_2\). Let \(U=D\cup C\cup((N(I)\cap V(W)))\setminus \{z_1,…z_{x_2}\})\) \[|U|\leq|D|+\sum\limits_{j=1}^{\Delta}ji_j+s_0-(x_1+x_2),\]and \[\omega(G-U)\geq\sum\limits_{j=1}^{\Delta}i_j+s_0+y.\]
Let \(t=t(G)\). We have \(d_{G-D}(x)\leq a\) for some \(x\in S\). Otherwise, \(d_{G-D}(x)\geq a+1\) for every \(x\in S\). Then \(q(D,S)\geq b|D|-a|S|+d_{G-D}(S)+1\geq b|D|+|S|+1\) and \(t<1<a-1+\frac{a}{b}\), a contradiction.
Claim 1. \(|U|\geq t\omega(G-U)\), if \(\omega(G-U)=1\) .
In fact, by Lemma 1.8, \(2t\leq d(x)\leq d_{G-D}(x)+|D|\) for all \(x\in S\). Thus choosing \(x\in S\) with \(d_{G-D}(x)\leq a\) we get \(|D|\geq 2t-a\) and \(|D|\geq t-1\geq1\) since \(t\geq a-1\). In the case \(C\neq\emptyset\), \(|U|\geq|D|+|C|\geq t\). Otherwise, we get \(C_1\cup\ldots\cup C_{\Delta-1}=\emptyset\), then \(S_1\cup\ldots\cup S_{\Delta-1}\) is an independent set. Since \(1=\omega(G-U)\geq\sum\limits_{j=1}^{\Delta}i_j+s_0\geq1,\) we have \(s_0=1\) or \(\sum\limits_{j=1}^{\Delta}i_j=1\). Obviously, if \(s_0=1\), \(G-S_0-D\neq\emptyset\). Otherwise, \(0>b|D|-a|S_0|+d_{G-D}(S_0)\geq b|D|-a>0,\) a contradiction. Thus \(|D|\geq t\omega(G-D)\geq2t\), since \(\omega(G-D)\geq\omega(G-D-S_0)+1\geq2\). Suppose that \(\sum\limits_{j=1}^{\Delta}i_j=1\), set \(i_1=1\), \(S_1=\{v\}\) and \(N_{G-D}(v)=\{u\}\). If \(N_G(u)-(D\cup S_1)\neq\emptyset\), then \(t\leq\frac{|D\cup u|}{\omega(G-(D\cup u))}\) and \(|D|\geq2t-1.\) Otherwise, there exists \(x\in D\) but \(x\notin N_G(u)\) or \(D\subseteq N_G(u)\), we have \(t\leq\frac{|(D\setminus x)\cup S_1|}{\omega(G-((D\setminus x)\cup S_1))}\) or \(d_G(u)=|D|+1\geq2t\) respectively. In all cases, \(|D|\geq t\), therefore \(|U|\geq|D|\geq t\omega(G-U)\).
If \(\omega(G-U)>1\), then \(|U|\geq t\omega(G-U)\) for \(G\) is \(t\)-tough. Therefore,\[s_0+|D|+\sum\limits_{j=1}^{\Delta}ji_j-(x_1+x_2)\geq t\left(\sum\limits_{j=1}^\Delta i_j+y+s_0\right).\]
And since \(\omega(G-D-S)\geq q(D,S)>b|D|-a|S|+d_{G-D}(S)\) we have
\[\begin{aligned} |D|&\ge \sum\limits_{j=1}^\Delta (t-j)i_j+(ty+x_1+x_2)+ts_0-s_0\\ &\geq \omega(G-D-S)+\sum\limits_{j=1}^\Delta (t-j)i_j(t-j)i_j+ts_0-s_0\\ &> b|D|-a|S|+d_{G-D}(S)+\sum\limits_{j=1}^\Delta (t-j)i_j (t-j)i_j+ts_0-s_0\\ &= b|D|-\sum\limits_{j=1}^\Delta(a-j)( i_j+c_j)\sum\limits_{j=1}^\Delta (t-j)i_j (t-j)i_j+ts_0-as_0-s_0\\ &\geq b|D|+\sum\limits_{j=1}^\Delta(t-a)i_j+\sum\limits_{j=1}^\Delta(j-a)c_j+ts_0-as_0-s_0\\ &\geq b|D|+\sum\limits_{j=1}^{a-1}(t-a)i_j+\sum\limits_{j=1}^{a-1}(j-a)c_j+(t-a-1)s_0. \end{aligned}\] \[\label{eq2} (b-1)|D|\leq\sum\limits_{j=1}^{a-1}(a-t)i_j+\sum\limits_{j=1}^{a-1}(a-j)c_j+(a-t+1)s_0. \tag{2}\]
Claim 2. \(|D\cup N(I')|\geq t\omega(G-(D\cup N(I')))\).
If \(\omega(G-(D\cup N(I')))\geq2\), it holds obviously.
If \(\omega(G-(D\cup N(I')))=1\), we have \(I'\neq\emptyset\), otherwise \(0=\sum\limits_{j=1}^{a-1}j(a-j)i_j\geq \sum\limits_{j=1}^{a-1}(a-j)c_j\geq0\), and \(C_1\cup…\cup C_{a-1}=\emptyset\). \(H=\emptyset\), and \(S\neq\emptyset\), so \(|S_0|=1\) or \(|S_j|=1\) for \(a+1\leq j\leq\Delta\). Both cases contradict to (1). Thus \(|I'|=1\).set \(I'=\{x\}\), then \(|D\cup N(x)|\geq d(x)\geq2t>t\omega(G-D\cup N(x))\).
Hence \[|D|+\sum\limits_{j=1}^{a-1}ji_j\geq t\left( \sum\limits_{j=1}^{a-1}i_j+s_0\right),\] and
\[\label{eq3} (b-1)|D|\geq \sum\limits_{j=1}^{a-1}(b-1)(t-j)i_j+(b-1)ts_0. \tag{3}\]
So from (2) and (3) we have \[\sum\limits_{j=1}^{a-1}(a-t)i_j+\sum\limits_{j=1}^{a-1}(a-j)c_j+(a-t)s_0\geq \sum\limits_{j=1}^{a-1}(b-1)(t-j)i_j+(b-1)ts_0,\] and \[\sum\limits_{j=1}^{a-1}(a-t)i_j+\sum\limits_{j=1}^{a-1}j(a-j)i_j\geq \sum\limits_{j=1}^{a-1}(b-1)(t-j)i_j+(bt-t-a+t)s_0,\] since \(\sum\limits_{j=1}^{a-1}(a-j)c_j\leq\sum\limits_{j=1}^{a-1}j(a-j)i_j\). As \(bt-t-a+t>0\), we have \(a-t+j(a-j)\geq(b-1)(t-j)\) and \(t<\frac{a+j^2-aj-bj+j}{b}\) for all \(j\), \(1\leq j\leq a-1\), which contradicts \(t\geq a-1+\frac{a}{b}\). ◻