An Extension of Cui-Kano’s Characterization Problem on 3 Graph Factors 1 0 2 Hongliang Lu∗ n a School of Mathematics and Statistics J 6 Xi’an Jiaotong University, Xi’an 710049,PR China 2 ] O C Abstract . h t Let G be a graph with vertex set V(G) and let H : V(G) → 2N be a set function a m associating with G. An H-factor of graph G is a spanning subgraphs F such that [ dF(v)∈H(v) for every v ∈V(G). 2 v Let f :V(G)→N be an eveninteger-valuedfunction such that f ≥4 and let H (v)= f 7 5 {1,3,...,f(v) − 1,f(v)} for v ∈ V(G). In this paper, we investigate Hf-factors of 6 graphs G by using Lov´asz’s structural descriptions. Let o(G) denote the number of 4 odd components of G. We show that if one of the following conditions holds, then G . 1 contains an H -factor. 0 f 3 (i) o(G−S)≤f(S) for all S ⊆V(G); 1 v: (ii) |V(G)| is odd, dG(v) ≥ f(v)−1 for all v ∈ V(G) and o(G−S) ≤ f(S) for all i ∅6=S ⊆V(G). X r As a corollary, we show that if a graph G with odd order and minimum degree 2n−1 a satisfies o(G−S)≤2n|S| for all ∅6=S ⊆V(G), then G contains an H -factor. In particular, we make progress on the characterization n problem for a special family of graphs proposed by Akiyama and Kano. 1 Introduction All graphs in this paper are simple. Let G be a graph with vertex set V(G) and edge set E(G). We denote the degree of v in G by d (v). The minimum degree in graph G will be G denoted by δ(G) and the maximum degree by △(G). The subgraph induced by the set S ∗ Corresponding email: [email protected] (H.Lu) 1 is denoted by G[S]. The number of components of graph G is denoted by ω(G) and the number of odd components of G by o(G). Let E (S,T) denote the set of edges of graph G G withoneendinS andtheother endinT ande (S,T) =|E (S,T)|. Thejoin G= G +G , G G 1 2 is the graph obtained from two vertex disjoint graphs G and G by joining each vertex in 1 2 G to every vertex in G . 1 2 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 (x) ∈ H(x) for every vertex x ∈ V(G). (1) F By specifying H(x) to be an interval or a special set, an H-factor becomes an f-factor, an [a,b]-factor or a (g,f)-factor, respectively. Let F be a spanning subgraph of G. Following Lov´asz [8], one may measure the “devi- ation” of F from the condition (1) by ∇H(F) = X min(cid:8)|dF(v)−h| : h∈ H(v)(cid:9). (2) v∈V(G) Moreover, the “solvability” of (1) can be characterized by ∇(H) = min{∇ (F) : F is a spanning subgraph of G}. H ThesubgraphF is said tobeH-optimal if ∇ (F) = ∇(H). Itis clear that F is an H-factor H if and only if ∇ (F) = 0, and any H-factor (if exists) is H-optimal. Let H Q = {h ,h ,...,h }, 1 2 m where h < h < ··· < h . Then Q is called an allowed set if each of the gaps of Q has at 1 2 m most one integer, i.e., h −h ≤ 2 for all 1 ≤ i≤ m−1. i+1 i A set function H associating with G is called an allowed set function (following [8]) if H(v) is an allowed set for all v ∈ V(G). Lov´asz [8]showed thatif H is notan allowed set, then thedecision problemof determin- ing whether a graph has an H-factor is known to be NP-complete. Cornu´ejols [3] provided the first polynomial algorithm for the problem with H allowed. A special case of H-factor problem is the so-called (1,h)-odd factor problem, i.e., the problem with H(v) = {1, 3,..., h(v)−2, h(v)}, 2 where h: V(G) → N be an odd function. For a constant odd integer n≥ 1, if h(x) = n for all x ∈ V(G), then (1,h)-odd factor is called (1,n)-odd 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.1 (Amahashi) Let n be an odd integer. A graph G has an (1,n)-odd factor if and only if o(G−S) ≤ n|S| for all subsets S ⊂ V(G). (3) For general odd value functions h, Cui and Kano [4] established a Tutte type theorem. Theorem 1.2 (Cui and Kano, [4]) Let h : V(G) → N be odd value function. A graph G has an (1,h)-odd factor if and only if o(G−S) ≤ h(S) for all subsets S ⊂ V(G). (4) Noticingtheformofthecondition(4),theyaskedthequestionofcharacterizinggraphsG in terms of graph factors such that o(G−S)≤ 2n|S| for all subsets S ⊂ V(G). (5) MotivatedbyCui-Kano’sproblem,LuandWang[9]considerthedegreeprescribedsubgraph problem for the special prescription H = {1,3,...,2n−1,2n}. (6) n Theorem 1.3 (Lu and Wang, [9]) Let G be a connected graph. If o(G−S)≤ 2n|S| for all subsets S ⊂ V(G), (7) then G contains an H -factor. n The condition of Theorem 1.3 implies that |V(G)| is even. Let H∗ = H ∪{−1}. For odd n n ordergraph,theyobtainedthefollowingresult(forconvenience, thedefinitionofH∗-critical n graph will be introduced in Section 2). Theorem 1.4 (Lu and Wang, [9]) Let G be a connected graph of odd order. Suppose that o(G−S) ≤ 2n|S| for all ∅ =6 S ⊂ V(G). (8) Then either G contains an H -factor, or G is H∗-critical. n n 3 The condition (4) implies that the graph is even order. For odd order graph, Akiyama and Kano propose the following problem (see also [1, Problem (6.14)] ). Problem 1.5 (Akiyama and Kano, [1]) Let G be a connected graph and h :V(G) → N be an even integer-valued function. If G satisfies o(G−S) ≤ h(S) for all ∅ =6 S ⊂ V(G), (9) what factor or property does G has? Let f ≥4 be an even integer-value function and let H : V(G) → 2N be an set function f such that H (v) = {1,3,...,f(v)−1,f(v)} for v ∈ V(G). Motivated by Akiyama-Kano’s f problem, we investigate the structure of graphs without H -factor by using Lov´asz’s H- f factorstructuretheory[8]. Weobtainthefollowingresult,whichisanextensionofTheorem 1.3. Theorem 1.6 Let G be a graph with even order. If o(G−S)≤ f(S) for all S ⊂ V(G), (10) then G contains an H -factor. f The inequality (10) also implies that |V(G)| is even. For odd order graph, we solve Problem 1.5 and obtain a stronger result than Theorem 1.4. Theorem 1.7 Let G be a connected graph with odd order. Suppose that d (v) ≥ f(v)−1 G for all v ∈ V(G). If o(G−S) ≤ f(S) for all ∅ =6 S ⊂ V(G), (11) then G contains an H -factor. f Corollary 1.8 Let n ≥ 2 be an integer and let G be a connected graph with odd order and minimum degree 2n−1. If o(G−S) ≤ 2n|S| for all ∅ =6 S ⊂ V(G), (12) then G contains an H -factor. n Remark 1: In Corollary 1.8, the conditions “δ(G) ≥ 2n−1” is sharp. Let K denote 2n−1 the complete graph of order 2n − 1. Take 2n − 2 disjoint copies of K . Add a new 2n−1 4 vertices v and connect two vertices in each copy of K to the new vertex v. This results 2n−1 a connected graph G with odd order (2n−2)(2n−1)+1 and minimum degree 2n−2. It is easy to show that o(G−S) ≤ 2n|S| for all ∅ =6 S ⊂ V(G). (13) Now we show that G contains no H -factor. Otherwise, suppose that G contains an H - n n factor F. By parity, K contains no H -factors and so F contains exactly an edge from 2n−1 n a copy of K . Then we have d (v) = 2n−1 ∈/ H , a contradiction. 2n−1 F n Remark 2: In Corollary 1.8, the condition (12) is not necessary for the existence of an H -factor in a graph. Let m ≥ 2n+2 be an even integer. Consider the graph n G = K +mK 1 2n+1 obtained by linking a vertex v to all vertices in 2n+1 copies of the complete graph K . 2n+1 Clearly, G is a graph with odd order and minimum degree 2n+1. It is easy to verify that G contains an H -factor. However, taking the subset S to be the single vertex v, we see n that the condition (12) does not hold for G. 2 On H-critical Graphs In this section, we study H-factors of graphs based on Lov´asz’s structural description to the degree prescribed subgraph problem. Denote by I (v) the set of vertex degrees in all H H-optimal subgraphs of graph G, i.e., I (v) = {d (v) : all H-optimal subgraphs F}. H F Comparing the set I (v) with H, one may partition the vertex set V(G) into four classes: H C = {v ∈ V(G) : I (v) ⊆ H(v)}, H H A = {v ∈ V(G)−C : minI (v) ≥ maxH(v)}, H H H B = {v ∈ V(G)−C : maxI (v) ≤ minH(v)}, H H H D = V(G)−A −B −C . H H H H It is clear that the 4-tuple (A ,B ,C ,D ) is a pairwise disjoint partition of V(G). We H H H H call it the H-decomposition of G. In fact, the four subsets can bedistinguished according to the contributions of their members to the deviation (2). A graph G is said to be H-critical if it is connected and D = V(G). For non-consecutive allowed set function, the only H 5 necessary condition of H-critical graph is given by Lov´asz [8]. In this paper, we obtain a sufficient condition for H-critical graph. We write MH(x) = maxH(x) and mH(x) = minH(x) for x ∈ V(G). For S ⊆ V(G), let MH(S) = MH(x) and mH(S) = mH(x). By the definition of Px∈S Px∈S A ,B ,C ,D , the following holds: H H H H (I) for every x ∈ B , there exists an H-optimal graph F such that d (x) < mH(x); H F (II) for every x ∈ A , there exists an H-optimal graph F such that d (x) > MH(x); H F (III) for every x ∈ D , there exists an H-optimal graph F such that d (x) < MH(x) and H F other H-optimal graph F′ such that d (x) > mH(x). F Lov´asz [8] gave the following properties. Lemma 2.1 (Lov´asz, [8]) IfGisasimple graph, thenI (v)isanintervalforallv ∈ D . H H Lemma 2.2 (Lov´asz, [8]) The intersection I (v)∩H(v) contains no consecutive integers H for any vertex v ∈ D . H Given an integer set P and an integer a, we write P −a = {p−a | p ∈ P}. Let C be a connected induced subgraph of G and T ⊆ V(G)−V(C). Let H : V(C) → 2N be a set C,T function such that H (x) = H(x)−e (x,T) for all x ∈ V(C). C,T G Lemma 2.3 (Lov´asz, [8]) Every component R of G[D ] is H -critical and if F is H R,BH H-optimal, then F[V(R)] is H -optimal. R,BH Lemma 2.4 (Lov´asz, [8]) If G is H-critical, then ∇(H) = 1. Lemma 2.5 (Lov´asz, [8]) For any H-optimal graph F, E (B ,B ∪C ) ⊆ E(F), and G H H H E (A ,C ∪A )∩E(F) = ∅. G H H H Theorem 2.6 (Lov´asz, [8]) ∇(H) = ω(G[D ])+ (mH(v)−d (v))− MH(v). H Pv∈BH G−AH Pv∈AH In the proof of main theorems, we need the following two technical lemmas. Lemma 2.7 Let F be an H-optimal subgraph. For every component R of G[D ], F misses H at most an edge of E (V(R),B ). G H 6 Proof. Let F be an H-optimal subgraph of G. We write τ = ω(G[D ]) and G[D ] = H H H C ∪ ··· ∪ C . Since C is H -critical, then C contains no H -factors. So if 1 τH i Ci,BH i Ci,BH def (C ) = 0, then F either misses at least an edge of E(C ,B ) or contains at least an F i i H edges of E(C ,A ). Let τ denote the number of components of G[D ] such that F misses i H B H at least an edge of E(C ,B ) and τ denote the number of the components of G[D] such i H A that F contains at least an edge of E(C ,A ). Let τ denote the number of components C i H c i of G[D ] such that F contains at least one edge of E(C ,A ) and misses at least one edge H i H E(C ,B ). Then we have i H ∇H(F) ≥ τH −τA−τB +τc+ X min{|r−dF(x)| | r ∈ H(x)} x∈AH∪BH ≥ τH −τA−τB +τc+ X (dF(x)−MH(x))+ X (mH(x)−dF(x)) x∈AH x∈BH ≥ τH −τA−τB +τc+(eF(AH,BH)+τA−MH(AH))+ X (mH(x)−dF(x)) x∈BH = τH −τB +τc+(eF(AH,BH)−MH(BH))+ X (mH(x)−dF(x)) x∈BH ≥ τH −τB +τc+(eF(AH,BH)−MH(AH))+(mH(BH)−(eF(AH,BH)+ X dG−AH(x)−τB)) x∈BH = τH(AH,BH)+τc+mH(BH)−MH(AH)− X dG−AH(x) ≥ ∇(H). x∈BH Since ∇ (F) = ∇(H), then we obtain τ = 0 and H c X dF(x) = eF(AH,BH)+ X dG−AH(x)−τBH, x∈BH x∈BH which implies that F misses at most an edge from C to B. This completes the proof for i 1 ≤ i≤ τ . 2 H Lemma 2.8 Let G be a graph and let H : V(G) be an allowed set function. If MH(v)−1 ∈ H(v) and d (v) ≥ MH(v)−1 for all v ∈ V(G), then G is not H-critical. G Proof. By contradiction, we firstly assume that G is H-critical. Let F be an H-optimal subgraph of G such that E(F) is maximal. SinceGisH-criticalandF isH-optimal,thenbyLemma2.4,wehaved (v) ≤ MH(v)+ F 1 for all v ∈ V(G). We claim that there exists a vertex x ∈ V(G) such that d (x) = F MH(x)+1. Otherwise, suppose that d (v) ≤ MH(v) for all v ∈ V(G). Then there exists F a vertex v ∈ V(G) such that d (v) ∈/ H(v) and so 0 ≤ d (v) ≤ f(v) − 2. Hence there F F exists an edge e ∈ E(G) − E(F), which is incident with vertex v. Then F ∪ {e} is also H-optimal, contradicting to themaximality of F. Thus there exists a vertex x ∈V(G) such 7 that d (x) = MH(x)+1. Since I (x) is an interval and I (x)∩H(x) contains no two F H H consecutive integers, then we have minI (x)≥ MH(x), contradicting to x ∈ D . H H This completes the proof. 2 Corollary 2.9 Let n ≥ 2 be an integer and let G be a graph. If δ(G) ≥ 2n−1, then G is not H -critical. n 3 The Proof of Theorems 1.6 and 1.7 In this section, we assume that f : V(G) → Z+ be an even integer-valued function such that f ≥4 and H (v) = {1,3,...,f(v)−1,f(v)} for all v ∈ V(G). f Theorem 3.1 Let G be a graph and let A , B , C and D be defined as above. Then H H H H f f f f (a) E (B ,B ∪C )= ∅; G H H H f f f (b) For every component R of G[D ], |V(R)|+|E (V(R),B )| ≡ 1 (mod 2); H G H f f (c) every component R of G[D ∪B ] is odd. H H f f Proof. Firstly, we prove (a) by contradiction. Suppose that there exists an edge e ∈ E (B ,B ∪C ). Without loss of generality, we assume that e = uv and u ∈ B . For G H H H H f f f f any H-optimal graph F, by Lemma 2.5, e ∈ E(F) and so d (v) ≥ 1, contradicting to the F definition of B . This completes the proof of (a). H f Secondly, we prove (b). By Lemma 2.3, R is H -critical. For simplicity, we write R,BHf H = H . We claim that f(u)−e (u,B ) ∈/ I (u) for all u ∈ V(R). Otherwise, R R,BHf G Hf HR suppose that there exists a vertex x ∈ V(R) such that f(x)−e (x,B ) ∈ I (x). By G Hf HR Lemma2.2,I (x)∩H (x)doesnotcontain twoconsecutive integersandsowehavef(x)− HR R 1−e (u,B ) ∈/ I (x). ByLemma2.1,I (x)isanintervalandsowehaveminI (x) ≥ G Hf HR HR HR MH (x), contradicting to the definition of H-critical graphs. Hence I (u) ⊆ [0,f(u)− R HR 1−e (u,B )]. Let F be an H -optimal graph and F∗ = F[V(R)]. By Lemma 2.3, F∗ G Hf f is an H -optimal subgraph of graph R. Furthermore, by Lemma 2.3, R is H -critical and R R so there exists a vertex x ∈ V(R) such that dF∗(x) ∈/ HR(x) and dF∗(y) ∈ HR(y) for all y ∈ V(R)−x. 8 Hence for every vertex y ∈ V(R) − x, dF∗(y) ≡ f(y) − 1 − eG(y,B) (mod 2) and dF∗(x) ≡ f(x)−2−eG(x,BH ) (mod 2). Then f X dF∗(v) ≡ X (f(y)−1−eG(y,BH ))+f(x)−2−eG(x,BH ) (mod 2) f f v∈V(R) y∈V(R)−x ≡ X eG(y,BH )+|V(R)|−1, f y∈V(R) which implies X eG(y,BH )+|V(R)| ≡ 1 (mod 2). f y∈V(R) This completes the proof of (b). Finally, we prove (c). We write B = {v ,...,v } and G[D ] = C ∪···∪C . For Hf 1 |BHf| Hf 1 τ 1 ≤ i ≤ |B | and 1 ≤ j ≤ τ, we claim e (v ,V(C )) ≤ 1. Otherwise, suppose that there H G i j f exists v ∈ B and a component C of G[D ] such that e (v,V(C )) ≥ 2. For arbitrary H i H G i f f H -optimal graph F, by Lemma 2.7, then we have d (v) ≥ 1, contradicting v ∈ B . f F Hf Let R be an arbitrary connected component of G[D ]. Without loss of generality, we H f write V(R) = C ∪···∪C ∪B , where B = {y ,...,y }. Now we construct a graph R∗ 1 k 1 1 1 r obtained from R by contracting C to a vertex x for 1 ≤ i ≤ k. By (a), R∗ is a bipartite i i graph. Claim 1. R∗ is a tree. Since R is connected, then R∗ is connected. Now we show that R∗ contains no cycles. Conversely, suppose that R∗ contains a cycle x y ,...,x y x . We write W = C ∪···∪ 1 1 m m 1 i1 C and B = {y ,...,y }. By Lemma 2.7, for any H-optimal graph F, F contains at im 2 1 m least m edges from W to B . Now we claim that d (v) = 1 for all v ∈B , otherwise, there 2 F 2 exists a vertex v ∈ B such that d (v) ≥ 2 contradicting to v ∈ B ⊆ B . Since F is 2 F 2 Hf an arbitrary H -optimal graph and d (v) = 1 for all v ∈ B , then we have B ⊆ C , a f F 2 2 Hf contradiction again. This completes Claim 1. LetW∗ =V(C )∪···∪V(C ). ByClaim1,R∗isatree,whichimpliesthate (W∗,B )= 1 k G 1 k+r−1. By (b), we have k k ≡ X(|V(Ci)|+eG(V(Ci),BH )) (mod 2) f i=1 k = X|V(Ci)|+eG(W∗,B1) i=1 k = X|V(Ci)|+k+r−1, i=1 9 which implies k X|V(Ci)|+r ≡ 1 (mod 2). i=1 Hence |V(R)| is odd. This completes the proof. 2 By Theorems 2.6 and 3.1, we obtain the following result. Corollary 3.2 If graph G contains no H -factors, then there exists two disjoint subsets f S,T of V(G) such that f(S)−|T|+XdG−S(x)−q(S,T) < 0, x∈T where q(S,T) denote the number of components C of G − S − T such that |V(C)| + e (V(C),T) ≡ 1 (mod 2). G Proof of Theorem 1.6. Since |V(G)| is even, by Theorem 3.1 (b), G is not H -critical. f By Lemma 3.1 (a) and (c), E (B ,C ) = ∅ and every component of G[D ∪B ] is G H H H H f f f f an odd component. We write ω(G[D ∪B ]) = k and G[D ∪B ] = R ∪...∪R . Hf Hf Hf Hf 1 k Without loss of generality, suppose that V(R )= V(C )∪···∪V(C )∪B for 1 ≤ i ≤ k, i i1 iri i where C is a component of G[D ] for 1 ≤ j ≤ r and B ⊆ B . By Theorem 2.6, ij H i i H f f Theorem 3.1 (c) and Claim 1 of Theorem 3.1, 0 < ∇(Hf)= ω(G[DHf])+|BHf|− X dG−AHf(x)−f(AHf) x∈BHf k = X(|Bi|+ri− X dG−AHf(x))−f(AHf) i=1 x∈Bi k = X(|Bi|+ri−eG(Bi,V(Ri)−Bi))−f(AH ) f i=1 = k−f(A ) H f = o(G[D ∪B ])−f(A ) H H H f f f ≤ o(G−A )−f(A ), H H f f a contradiction. This completes the proof. 2 Proof of Theorem1.7. ByLemma2.8,GisnotH -critical. ThenwehaveA ∪B 6= ∅. f Hf Hf For every component C of G[D ] and every vertex v, we claim E (C ,v) ≤ 1. Otherwise, i H G i f suppose that e (C ,v) ≥ 2. By Lemma 2.7, we have d (v) ≥ 1 for any H -optimal graph G i F f F, contradicting to v ∈B . H f 10