Hongliang Lua , Yuqing Linb
aDepartment of Mathematics Xi'an Jiaotong University, Xi'an 710049, PR China bSchool of Electrical Engineering and Computer Science, The University of Newcastle, Australia
luhongliang215@sina.com, yuqing.lin@newcastle.edu.au
In this paper, we obtain a sufficient condition for the existence of parity factors in a regular graph in terms of edge-connectivity. Moreover, we also show that our condition is sharp.
Keywords: Parity Factors, edge-connectivity Mathematics Subject Classification : 05C70
1. Preliminaries
Let G = (V, E) be a graph with vertex set V (G) and edge set E(G). The number of vertices of a graph G is called the order of G and is denoted by n. The number of edges of G is called the size of G and is denoted by e. For a vertex v of graph G, the number of edges of G incident to v is called the degree of v in G and is denoted by dG(v). For two subsets S, T ⊆ V (G), let eG(S, T) denote the number of edges of G joining S to T.
Let H be a function associating a subset of Z to each vertex of G. A spanning subgraph F of graph G is called an H-factor of G if
\[d_F(x) \in H(x)\] for every vertex \(x \in V(G)\). (1)
For a spanning subgraph F of G and for a vertex v of G, define
\[\delta(H; F, v) = \min\{|d_F(v) - i| i \in H_v\},\\]
Received: 6 February 2013, Revised: 8 April 2013, Accepted: 24 April 2013.
and let δ(H; F) = P x∈V (G) δ(H; F, x). Thus a spanning subgraph F is an H-factor if and only if δ(H; F) = 0. Let
\[\delta_H(G) = \min\{\delta(H; F) \mid F \text{ are spanning subgraphs of } G\}.\]
A spanning subgraph F is called H-optimal if δ(H; F) = δH(G). The H-factor problem is to determine the value δH(G). An integer h is called a gap of H(v) if h /∈ H(v) but H(v) contains an element less than h and an element greater than h. Lovasz [11] gave a structural description on ´ the H-factor problem in the case where H(v) has no two consecutive gaps for all v ∈ V (G) and showed that the problem is NP-complete without this restriction. Moreover, he also conjectured that the decision problem of determining whether a graph has an H-factor is polynomial in the case where H(v) has no two consecutive gaps for all v ∈ V (G). Cornuejols [5] proved the conjecture. ´
Let therefore g, f : V → Z + such that g(v) ≤ f(v) and g(v) ≡ f(v) (mod 2) for every v ∈ V . Then a spanning subgraph F of G is called a (g, f)-parity-factor, if g(v) ≤ dF (v) ≤ f(v) and dF (v) ≡ f(v) (mod 2) for all v ∈ V . Clearly, a (g, f)-parity-factor is a special kind of H-factor and it has been shown that the decision problem of determining whether a graph has a (g, f)-parity factor is polynomial.
Let a, b be two integers such that 1 ≤ a ≤ b and a ≡ b (mod 2). If g(v) = a and f(v) = b for all v ∈ V (G), then a (g, f)-parity-factor is called an (a, b)-parity factor. Let n ≥ 1 be odd. If a = 1 and b = n, then an (a, b)-parity factor is called a (1, n)-odd factor. There is also a special case of the (g, f)-factor problem which is called the even factor problem, i.e., the problem with g(v) = 2, f(v) ≥ |V (G)| and f(v) ≡ g(v) (mod 2) for all v ∈ V (G).
Fleischner gave a sufficient condition for a graph to have an even factor in terms of edge connectivtiy.
Theorem 1.1 (Fleischner,[8]; Lovasz, [12]) ´ . If G is a bridgeless graph with δ(G) ≥ 3, then G has an even factor.
For a general graph G and an integer k, a spanning subgraph F such that
\[d_F(x) = k \text{ for all } x \in V(G)\]
is called a k-factor. In fact, a k-factor is also a (k, k)-parity factor.
The first investigation of the (1, n)-odd factor problem is due to Amahashi [2], who gave a Tutte type characterization for graphs having a global odd factor.
Theorem 1.2 (Amahashi). Let n be an odd integer. A graph G has a (1, n)-odd factor if and only if
\[o(G-S) \le n|S|\] for all subsets \(S \subset V(G)\). (2)
For general odd value functions h, Cui and Kano [6] established a Tutte type of theorem.
Theorem 1.3 (Cui and Kano, [6]). Let h : V (G) → N be odd value function. A graph G has a (1, h)-odd factor if and only if
\[o(G-S) \le h(S)\] for all subsets \(S \subset V(G)\). (3)
Now there are many results on consecutive factors (i.e. (g, f)-factor). But the research progress on non-consecutive factors is slow. In non-consecutive factor problems, (g, f)-parity factors have many similar properties with k-factors. So we believe that many results on k-factors can be extended to (g, f)-factor. In this paper, we will extend a result on k-factors of regular graphs to the (g, f)-parity-factors.
Now let us recall one of the classical results due to Petersen.
Theorem 1.4 (Petersen [13]). Let r and k be integers such that 1 ≤ k ≤ r. Every 2r-regular graph has a 2k-factor.
Considering the edge-connectivity, Gallai [7] proved the following result.
Theorem 1.5 (Gallai [7]). Let r and k be integers such that 1 ≤ k < r, and G an m-edgeconnected r-regular graph, where m ≥ 1. If one of the following conditions holds, then G has a k-factor.
- (i) r is even, k is odd, |G| is even, and r m ≤ k ≤ r(1 − 1 m );
- (ii) r is odd, k is even and 2 ≤ k ≤ r(1 − 1 m );
- (iii) r and k are both odd and r m ≤ k.
Bollobas, Satio and Wormald [3] improved above the result. ´
Theorem 1.6 (Bollobas, Saito and Wormald ) ´ . Let r and k be integers such that 1 ≤ k < r, and G be an m-edge-connected r-regular graph, where m ≥ 1 is a positive integer. Let m∗ ∈ {m, m+1} such that m∗ ≡ 1 (mod 2). If one of the the following conditions holds, then G has a k-factor.
- (i) r is odd, k is even and 2 ≤ k ≤ r(1 − 1 m∗ );
- (ii) r and k are both odd and r m∗ ≤ k.
In this paper, we extend Theorems 1.5 and 1.6 to (a, b)-factors. The main tool in our proofs is the following theorem of Lovasz (see[11]). ´
Theorem 1.7 (Lovasz [11]) ´ . G has a (g, f)-parity factor if and only if for all disjoint subsets S and T of V (G),
\[\delta(S,T) = f(S) + \sum_{x \in T} d_G(x) - g(T) - e_G(S,T) - \tau \ge 0,\]
where τ denotes the number of components C, called f-odd components of G − (S ∪ T) such that eG(V (C), T) + f(V (C)) ≡ 1 (mod 2). Moreover, δ(S, T) ≡ f(V (G)) (mod 2).
2. Main Theorem
Theorem 2.1. Let a, b and r be integers such that \(1 \le a \le b < r\) and \(a \equiv b \pmod{2}\). Let G be an m-edge-connected r-regular graph with n vertices. Let \(m^* \in \{m, m+1\}\) such that \(m^* \equiv 1 \pmod{2}\). If one of the following conditions holds, then G has an (a, b)-parity factor.
- (i) r is even, a, b are odd, |G| is even, \(\frac{r}{m} \leq b\) and \(a \leq r(1 \frac{1}{m})\);
- (ii) r is odd, a, b are even and \(a \le r(1 \frac{1}{m^*})\);
- (iii) r, a, b are odd and \(\frac{r}{m^*} \leq b\).
By Theorem 1.6, (ii) and (iii) are true. Now we prove (i). Let \(\theta_1 = \frac{a}{r}\) and \(\theta_2 = \frac{b}{r}\). Then \(0 < \theta_1 \le \theta_2 < 1\). Suppose that G contains no (a,b)-parity factors. By Theorem 1.7, there exist two disjoint subsets S and T of V(G) such that \(S \cup T \ne \emptyset\), and
\[-2 \ge \delta(S,T) = b|S| + \sum_{x \in T} d_G(x) - a|T| - e_G(S,T) - \tau, \tag{4}\]
where \(\tau\) is the number of a-odd (i.e. b-odd) components C of \(G-(S\cup T)\). Let \(C_1, \dots, C_{\tau}\) denote a-odd components of G-S-T and \(D=C_1\cup\dots\cup C_{\tau}\).
Note that
\[\begin{split} -2 &\geq \delta(S,T) = b|S| + \sum_{x \in T} d_G(x) - a|T| - e_G(S,T) - \tau \\ &= b|S| + (r-a)|T| - e_G(S,T) - \tau \\ &= \theta_2 r|S| + (1-\theta_1)r|T| - e_G(S,T) - \tau \\ &= \theta_2 \sum_{x \in S} d_G(x) + (1-\theta_1) \sum_{x \in T} d_G(x) - e_G(S,T) - \tau \\ &\geq \theta_2 (e_G(S,T) + \sum_{i=1}^{\tau} e_G(S,C_i)) + (1-\theta_1)(e_G(S,T) + \sum_{i=1}^{\tau} e_G(T,C_i)) - e_G(S,T) - \tau \\ &= \sum_{i=1}^{\tau} (\theta_2 e_G(S,C_i) + (1-\theta_1)e_G(T,C_i) - 1) + (\theta_2 - \theta_1)e_G(S,T) \\ &\geq \sum_{i=1}^{\tau} (\theta_2 e_G(S,C_i) + (1-\theta_1)e_G(T,C_i) - 1). \end{split}\]
Since G is connected and \(0 < \theta_1 \le \theta_2 < 1\), so \(\theta_2 e_G(S, C_i) + (1 - \theta_1) e_G(T, C_i) > 0\) for each \(C_i\). Hence we will obtain a contradiction by showing that for every \(C = C_i\), \(1 \le i \le \tau\), we have
\[\theta_2 e_G(S, C) + (1 - \theta_1) e_G(T, C) \ge 1.\] (5)
These inequalities imply
\[-2 \ge \delta_G(S, T) \ge \sum_{i=1}^{\tau} (\theta_2 e_G(S, C_i) + (1 - \theta_1) e_G(T, C_i) - 1)\] \[> \sum_{i=1}^{\tau-2} (\theta_2 e_G(S, C_i) + (1 - \theta_1) e_G(T, C_i) - 1) - 2 \ge -2,\]
which is impossible.
Now, we will prove the 5 is true. Since C is an a-odd component of G − (S ∪ T), we have
\[a|C| + e_G(T,C) \equiv 1 \pmod{2}.\] (6)
Moreover, since
\[r|C| = \sum_{x \in V(C)} d_G(x) = e_G(S \cup T, C) + 2|E(C)|,\]
we have
\[r|C| = e_G(S \cup T, C) \pmod{2}. \tag{7}\]
It is obvious that the two inequalities eG(S, C) ≥ 1 and eG(T, C) ≥ 1 imply
\[\theta_2 e_G(S, C) + (1 - \theta_1)e_G(T, C) \ge \theta_2 + 1 - \theta_1 = 1.\]
Hence we may assume eG(S, C) = 0 or eG(T, C) = 0.
We consider the condition (i). If eG(S, C) = 0, then eG(T, C) ≥ m. Since a ≤ r(1 − 1 m ), then θ1 ≤ 1 − 1 m and so 1 ≤ (1 − θ1)m. By substituting eG(T, C) ≥ m and eG(S, C) = 0 into (5), we have
\[(1 - \theta_1)e_G(T, C) \ge (1 - \theta_1)m \ge 1.\]
If eG(T, C) = 0, then eG(S, C) ≥ m. Since r m ≤ b, hence θ2m ≥ 1, and so we obtain
\[\theta_2 e_G(S, C) \ge \theta_2 m \ge 1.\]
Consequently, condition (i) guarantees (5) holds and thus (i) is true. The proof is completed. Remark: The edge connectivity conditions in Theorem 2.1 are sharp.
We will give the construction for condition (i) of Theorem 2.1. For (ii) and (iii), the constructions are similar. Let r ≥ 2 be an even integer, a, b ≥ 1 two odd integers and 2 ≤ m ≤ r − 2 an even integer such that b < r/m or r(1 − 1 m ) < a. Since G has an (a, b)-parity factor if and only if G has an (r − b, r − a)-parity factor, so we can assume b < r/m. Let J(r, m) be the complete graph Kr+1 from which a matching of size m/2 is deleted. Take r disjoint copies of J(r, m). Add m new vertices and connect each of these vertices to a vertex of degree r − 1 of J(r, m). This gives an m-edge-connected r-regular graph denoted by G. Let S denote the set of m new vertices and T = ∅. Let τ denote the number of components C, which are called a-odd components of G − (S ∪ T) and eG(V (C), T) + a|C| ≡ 1 (mod 2). Then we have τ = r, and
\[\delta(S,T) = b|S| + \sum_{x \in T} d_{G-S}(x) - a|T| - \tau(S,T) = bm - r < 0.\]
So by Theorem 1.7, G contains no (a, b)-parity factors.
Acknowledgement
This work was supported by the National Natural Science Foundation of China (No. 11101329)
- [1] J. Akiyama and M. Kano, Factors and factorizations of graphs-a survey, J. Graph Theory, 9 (1985), 1-42.
- [2] A. Amahashi, On factors with all degree odd, Graphs and Combin., 1 (1985), 111–114.
- [3] B. Bollobas, A. Satio, and N. C. Wormald, Regular factors of regular graphs, ´ J. Graph Theory, 9 (1985), 97-103.
- [4] L. Collatz and U. Sinogowitz, Spektren endlicher Grafen, Abh. Math. Sem. Univ. Hamburg, 99 (2009), 287-297.
- [5] G. Cornuejols, General factors of graphs, ´ J. Combin. Theory Ser. B, 45 (1988), 185-198.
- [6] Y. Cui and M. Kano, Some results on odd factors of graphs, J. Graph Theory, 12 (1988), 327–333.
- [7] T. Gallai, The factorisation of graphs, Acta Math. Acad. Sci. Hung, 1 (1950), 133-153.
- [8] H. Fleischner, Spanning Eulerian subgraphs, the Splitting Lemma, and Petersen's Theorem, Discrete Math., 101 (1992), 33–37.
- [9] C. Godsil and G. Royle, Algebraic Graph Theory, Springer Verlag New York, (2001).
- [10] M. Kano, [a, b]-factorization of a graph. J. Graph Theory, 9 (1985), 129-146.
- [11] L. Lovasz, The factorization of graphs, II, ´ Acta Math. Sci. Hungar., 23 (1972), 223-246.
- [12] L. Lovasz, Combinatorial Problems and Exercises, North-Holland, Amsterdam (1979). ´
- [13] J. Petersen, Die Theorie der regularen Graphen, ¨ Acta Math., 15 (1891), 193-220.
- [14] W. T. Tutte, The factors of graphs, Canad. J. Math., 4 (1952), 314-328.