Convexity of Degree Sequences R. P. Anstee,1 Yunsun Nam2 1 DEPARTMENT OF MATHEMATICS UNIVERSITY OF BRITISH COLUMBIA #121-1984 MATHEMATICS ROAD VANCOUVER, B.C. CANADA, V6T 1Y4 2 DEPARTMENT OF MATHEMATICS EWHA WOMANS UNIVERSITY SEOUL 120-750, KOREA Received June 6, 1996; accepted August 25, 1998 Abstract: We explore the convexity of the set of vectors consisting of degree sequences of subgraphs of a given graph. Results of Katerinis and Fraisse, Hell c 1999 John Wiley and Kirkpatrick concerning vertex deleted f -factors are generalized. & Sons, Inc. J Graph Theory 30: 147–156, 1999 Keywords: f-factors, k-factors, matching, degree sequences, jump systems 1. CONVEXITY THEOREMS This article explores theorems that give the existence of a factor of a graph G as a consequence of the existence of other factors. Motivation was provided by convexity ideas. Let G = (V, E) be a multigraph, possibly with loops, with λ(e) denoting the multiplicity of e and dG (v) denoting the degree of vertex v in G. Let f = (f (v) : v ∈ V ) be given. An f -factor is a spanning subgraph H of G with dH (v) = f (v). A fractional spanning subgraph of G is given by a vector x = (x(e) : e ∈ E) with 0 ≤ x(e)P ≤ λ(e). We can discuss a fractional f factor by defining dx (v) = 2x(v, v) + u6=v x(v, u). Finding fractional f -factors Correspondence to: Y. Nam namy@math.ewha.ac.kr Grant sponsor: NSERC, GARC, and KRF. c 1999 John Wiley & Sons, Inc. CCC 0364-9024/99/020147-10 148 JOURNAL OF GRAPH THEORY is equivalent to finding network flows, e.g., [1]. We are now allowing fractional entries in f . Consider the polyhedron fract(G) = {f ∈ R|V | : G has a fractional f -factor}. (1.1) It is easy to verify that fract(G) is convex. In contrast, define factor(G) = {f ∈ R|V | : G has an f -factor}. (1.2) We call integer grid points in R|V | even grid points if the sum of their coordinates is even. Then factor(G) ⊆ fract(G) ∩ even grid points. (1.3) The set factor(G) has been studied before, most notably in terms of jump systems, an axiomatic generalization of matroids introduced by Bouchet and Cunningham [3] and further studied by Lovász [8]. Our idea in this article is to consider conditions where the convexity of fract(G) carries over to factor(G). Sometimes things work very well. The following theorem of Fulkerson, Hoffman and McAndrew [5] stated in our language is useful. Theorem 1.1 [5]. Let G, f be given. Assume f is an even grid point. Assume that G has the odd cycle property: every pair of vertex disjoint odd cycles in G are joined by an edge. Then G has a fractional f -factor if and only if G has an f -factor. The case G = Kn is the most interesting, since f -factors of Kn correspond to simple graphs with degree sequence given by f . Corollary 1.1. only if A graph G has the odd cycle property of Theorem 1.1 if and factor(G) = fract(G) ∩ even grid points. Proof. If G contains the union of two vertex disjoint odd cycles C1 , C2 not joined by an edge, then we can find an even grid point f in fract(G) not in factor(G); namely set f (v) = 1 for v ∈ V (C1 ) ∪ V (C2 ), f (v) = 0 otherwise. This works even for loops that are odd cycles. We rephrase the result in terms of convexity. Corollary 1.2. Let G have thePodd cycle property of Theorem 1.1. Let fi ∈ factor (G) for i = 1, 2, . . . , p with pi=1 ai fi = f for some even grid point f where Pp i=1 ai = 1 and 0 ≤ ai ≤ 1 for i = 1, 2, . . . , p. Then f ∈ factor (G). This ‘convexity’ of factor(G) can still hold for graphs G that do not have the odd cycle property if we introduce restrictions (with respect to G) on the f and the fi ’s we consider. In this section, we achieve the conclusions of Corollary 1.2 by adding restrictions mostly concerning the vertices where f (v) − fi (v) is odd. In Section P 2, we consider the possibility of a small difference between pi=1 ai fi and f . In Section 3, we generalize some previous results on vertex deleted f -factors into our setting and offer a convexity motivation that gives us some insight into these results. CONVEXITY OF DEGREE SEQUENCES 149 The following two theorems are our main results and are immediately followed by corollaries to indicate how you might apply the theorems. For U ⊆ V , we use the notation G[U ] for the subgraph of G induced by U . In the following, note that ai > 0. P (G) for i = 1, 2, . . . , p with pi=1 ai fi = f for Theorem 1.2. Let fi ∈ factor Pp some even grid point f where i=1 ai = 1 and 0 < ai ≤ 1 for i = 1, 2, . . . , p. For each i = 1, 2, . . . , p, let Ui be the set of vertices for which the corresponding coordinates of f − fi have odd entries and assume that for each i G[Ui ] has at most one pair of vertices {xi , yi } not joined. Assume that either (i) for at least one i either |Ui | = 0 or G[Ui ] is complete, or (ii) G[∪pi=1 {xi , yi }] is connected. Then f ∈ factor(G). Note that in the following result it is allowed to have a1 = 0 and/or a2 = 0. P Theorem 1.3. Let fi ∈ factor (G) for i = 1, 2, . . . , p with pi=1 ai fi = f for Pp some even grid point f, where i=1 ai = 1 and 0 ≤ ai ≤ 1 for i = 1, 2, . . . , p. Let f − fi = si = (si (1), si (2), . . . , si (|V |)) and assume all the odd entries occur in coordinates corresponding to vertex 1 or its neighbors in G. Assume that s1 (1) ≥ |V | X j=2 |s1 (j)|, s2 (1) ≤ − |V | X |s2 (j)|. (1.4) j=2 Then f ∈ factor(G). The following theorem of Katerinis was a motivating example. Corollary 1.3 [7]. Let m, n, l be three odd integers such that m < l < n. If G has subgraphs regular of degree m and n, then G has a subgraph regular of degree l. n−l Proof. Take f1 = (m, m, . . . , m), f2 = (n, n, . . . , n) and a1 = n−m , a2 = l−m n−m so that f = (l, l, . . . , l) satisfies the hypotheses of Theorem 1.2 (i). Assume G is a graph with all degrees being a multiple of k . Then we can ask if G has a subgraph (denoted ka G) satisfying a d(a/k)G (v) = dG (v) for all v in V. (1.5) k Thus, for example, G might be edge decomposed into k such k1 G subgraphs. Such questions were explored in [2]. Generalizing Corollary 1.3 due to Katerinis, we obtain the following. Corollary 1.4. Let G be given. Assume m, l, n are odd integers with m < l < n. Let f be an even grid point. If mf, nf ∈ factor(G), then lf ∈ factor(G). In n particular, if all degrees in G are multiples of a given k and G has m k G, k G subgraphs, then G has an kl G subgraph. We can also obtain a new existence result for k1 G subgraphs that generalizes Petersen’s theorem that a graph which is regular of degree 2k contains a 2-factor. 150 JOURNAL OF GRAPH THEORY Corollary 1.5. Let G, k be given. Assume that all degrees in G are multiples of k. Assume that the vertices with dG (v) ≡ k (mod 2k ) induce a complete graph. Then G has a subgraph k1 G. Proof. Let f1 be the degree sequence of the graph and let f2 = (0, 0, . . . , 0). Then f = k1 f1 + k−1 k f2 and in the notation of Theorem 1.2 (i), U1 ⊆ U2 and U2 = {v ∈ V : dG (v) ≡ k (mod 2k )}. We denote ei by the vector with a 1 in coordinate i and 0’s elsewhere as in linear algebra. This does not refer to the ith edge. The following results consider versions of Corollary 1.2 for general graphs where the vectors fi ∈ R|V | are close neighbors (hamming distance 2). The first result (i) is an axiom of jump systems and so follows from the fact that [3] showed that factor(G) is a jump system. Corollary 1.6. (i) If f + 2ei , f − 2ei ∈ factor(G), then f ∈ factor(G). (ii) If f + ei + ej , f − ei − ej ∈ factor(G) and (i, j) ∈ E(G), then f ∈ factor(G). (iii) If f + ei − ej , f − ei + ej ∈ factor(G) and (i, j) ∈ E(G), then f ∈ factor(G). Proof. In (i) we can take f1 = f − 2ei , f2 = f + 2ei and use Theorem 1.2 or 1.3. Cases (ii) and (iii) follow similarly. There are counterexamples to Corollary 1.6 (ii) and (iii) if the edge (i, j) is not present. In the notation of the proofs of our Theorems, which follow, counterexamples arise from i, j lying in different odd components for some S, T . Corollary 1.7. Let G be a connected graph with |V | = 2m, f = (1, 1, . . . , 1) and assume f − e2i−1 + e2i , f + e2i−1 − e2i ∈ factor(G) for i = 1, 2, . . . , m. Then G has a perfect matching (f ∈ factor(G)). Proof. We use Theorem 1.2 (ii) and obtain ∪Ui = V . P Corollary 1.8. Let fi ∈ factor (G) for i = 1, 2, . . . , p with pi=1 ai fi = f for Pp some even grid point f where i=1 ai = 1 and 0 ≤ ai ≤ 1 for i = 1, 2, . . . , p. Let f − e1 − e2 , f + e1 + e3 ∈ factor(G) with (1, 2), (1, 3) ∈ E(G). Assume all the odd entries of f − fi occur in coordinates corresponding to vertex 1 or its neighbors in G for each i = 1, 2, . . . , p. Then f ∈ factor(G). Proof. Use Theorem 1.3 with fp+1 = f − e1 − e2 , fp+2 = f + e1 + e3 and ap+1 = ap+2 = 0. Reorder so p + 1, p + 2 become 1, 2. To prove Theorems 1.2, 1.3 we use P Tutte’s existence theorem for f -factors. Also, for S, T ⊆ V , we let λ(S, T ) denote {λ(s, t) : s ∈ S, t ∈ T }. Theorem 1.4 [9]. Let G, f be given. Then G has an f -factor if and only if for all sets S, T ⊆ V with S ∩ T = ∅ we have X f (s) ≥ s∈S X t∈T f (t) − X dG (t) + λ(S, T ) + h(S, T ), (1.6) t∈T where h(S, T ) denotes the number of components C in G[V − (S ∪ T )] that are odd, where a component is considered odd if X c∈C f (c) + λ(C, T ) ≡ 0 (mod 2). (1.7) CONVEXITY OF DEGREE SEQUENCES 151 Some notation is useful in (1.6) when using fi instead of f . Let ∆i S = P − f (s)) and ∆i T = t∈T (fi (t) − f (t)). Let hi (S, T ) denote the number of odd components of G[V − (S ∪ T )] with respect to fi in (1.6) and ∆i h(S, T ) = hi (S, T ) − h(S, T ). In this section, we consider cases where conditions on G, f , and the fi ’s ensure that |∆i h(S, T )| ≤ 1. The following observation of Tutte is useful. P s∈S (fi (s) Theorem 1.5 [9]. X s∈S f (s) ≡ X t∈T If f is an even grid point, then in (1.6), f (t) − X dG (t) + λ(S, T ) + h(S, T ) (mod 2). (1.8) t∈T Proof of Theorem 1.2. Assume f 6∈ factor(G) and let S, T be a pair for which (1.6) is violated. Use the notation above. Consider a fixed i ∈ {1, 2, . . . , p}. When f changes to fi , components of G[V − (S ∪ T )] change their parity in (1.6) if they contain an odd number (≥ 1) of vertices from Ui . Since G[Ui ] has at most one pair of vertices not joined, we deduce that −2 ≤ ∆i h(S, T ) ≤ 2. (1.9) Since fi ∈ factor(G) and, using the parity argument of Theorem 1.5, ∆i S − ∆i T − ∆i h(S, T ) ≥ 2. P (1.10) P But pi=1 ai (∆i S − ∆i T ) = 0 and so pi=1 ai ∆i h(S, T ) ≤ −2. Using the strict inequality ai > 0 for i = 1, 2, . . . , p we deduce ∆i h(S, T ) = −2 for all i = 1, 2, . . . , p. Thus, condition (i) is contradicted. Under condition (ii), ∪pi=1 {xi , yi } ⊆ V − (S ∪ T ). Now G[∪pi=1 {xi , yi }] is connected, so {xi , yi } are in the same component of G[V − (S ∪ T )], which results in −1 ≤ ∆i h(S, T ), a contradiction. Thus, f ∈ factor(G). We could improve on Theorem 1.2 (i) in the following way. Let bi be the independence number of G[Ui ]; namely the maximumP number of mutually nonadjacent vertices. Then −bi ≤ ∆i h(S, T ) ≤ bi . Assume pi=1 ai bi < 2 (i.e., most of bi ’s are 1 or 2). But we are forced by our inequality to have the sum be ≥ 2 and so we will get a contradiction. Proof of Theorem 1.3. Assume f 6∈ factor(G) and let S, T be a pair for which (1.6) is violated. Use the notation of Theorem 1.2. We deduce from f1 ∈ factor(G) and Theorem 1.5 that 1 6∈ S . Similarly from f2 we have that 1 6∈ T . But then 1 ∈ V − (S ∪ T ), so there is only one component of G[V − (S ∪ T )] containing vertices with odd entries in si . Thus, −1 ≤ ∆i h(S, T ) ≤ 1 for any i = 1, 2, . . . , p and so as in Theorem 1.2 we get a contradiction. Thus, f ∈ factor(G). We could improve on Theorem 1.3 by imposing conditions to have more vertices forced in V − (S ∪ T ). 152 JOURNAL OF GRAPH THEORY 2. SMALL ERRORS CAN BE OVERCOME If f is an even grid point, then we can define the fractional deficiency of an f 0 with respect to f as the L1 norm kf 0 − f k1 = |V | X |f 0 (i) − f (i)|. (2.1) i=1 Given G, f we may define δ ∗ (f ) = min{kf 0 − f k1 : f 0 ∈ fract(G)}. (2.2) From results in [1] or otherwise, we can deduce the following. Proposition 2.1. If f is an even grid point, then δ ∗ (f ) is a nonnegative integer. If G is bipartite, then δ ∗ (f ) is a nonnegative even integer. We can use this by noting that if f 0 ∈ fract(G) and f is an even grid point with kf 0 − f k1 < 1, then δ ∗ (f ) < 1 and so δ ∗ (f ) = 0. Proposition 2.2. If f 0 ∈ fract(G), f is an even grid point with kf 0 − f k1 < 1 (or < 2 if G is bipartite) then f ∈ fract(G). This gives us an ability to ‘grow’ fract(G) from a subset of it, which is an idea explored for factor(G) in Section 3. For example, if f1 = f −2ei ∈ fract(G−(i, j)) and f2 = f − 2ej ∈ fract(G), then we see that f3 = f1 + ei + ej ∈ fract(G) (by adding the edge (i, j)) and k( 23 f3 + 13 f2 ) − f k1 = 23 < 1, hence f ∈ fract(G). Proposition 2.3. We may replace the condition P k pi=1 ai fi − f k1 < 1 in Theorem 1.3. Pp i=1 ai fi = f by the condition P Proof. We use pi=1 ai (∆i S − ∆i T ) < 1. We are unable to do the replacement in Theorem 1.2 (ii), because there we need to deduce that ∆i h(S, T ) = −2 for all i. However, the following result holds. P for i = 1, 2, . . . , p with k pi=1 ai fi −f k1 < 1 Theorem 2.1. Let fi ∈ factor(G) Pp for some even grid point f, where i=1 ai = 1 and 0 ≤ ai ≤ 1 for i = 1, 2, . . . , p. For each i = 1, 2, . . . , p, let Ui be the set of vertices for which the corresponding coordinates of f −fi have odd entries. Assume G[Ui ] is complete for i = 1, 2, . . . , p. Then f ∈ factor(G). Proof. Since G[Ui ] is complete, we deduce that −1 ≤ ∆i h(S, T ) ≤ 1 and so i=1 ai ∆i h(S, T ) ≥ −1. Pp 3. VERTEX DELETED f -FACTORS A variety of results in a similar vein have been proven, where fi = f − f (i)ei . We can think of an fi -factor of G as an f -factor of G − i, the vertex deleted subgraph, CONVEXITY OF DEGREE SEQUENCES 153 where it is understood that the new f has one fewer coordinate skipping over f (i). Let us use that notation. The result that, if (u, v) ∈ E and G − u, G − v have 2-factors then G has a 2-factor, has striking applications [6]. The following result generalizes results of Katerinis [7] and Fraisse, Hell, and Kirkpatrick [4]. Our result arises from focusing on factor(G). Theorem 3.1. Let {1, 2, . . . , p} ⊆ V and let ki be an even positive integer for i = 1, 2, . . . , p. Let G[{1, 2, . . . , p}] have a subgraph H with 2|E(H)| ≥ k1 . Assume f1 = f − k1 e1 ∈ factor(G − E(H)), fi = f − ki ei ∈ factor(G) for i = 2, 3, . . . , p. Then f ∈ factor(G). Proof. Assume f 6∈ factor(G) and let S, T be a pair for which (1.6) is violated. Use the notation of Theorem 1.2. Note that ∆i h(S, T ) = 0, since ki is even. Also f1 ∈ factor(G). Using fi ∈ factor(G) and Theorem 1.5, we deduce that i ∈ T for i = 1, 2, . . . , p. But then (1.6) is violatedP for f replaced by f1 and G replaced by P G − E(H), since t∈T dG−E(H) (t) ≤ ( t∈T dG (t)) − k1 , yet the sum λ(S, T ) and h(S, T ) are unaffected. Hence, f1 6∈ factor(G − E(H)), a contradiction. Thus, f ∈ factor(G). Note that if both f − ki ei and f ∈ factor(G), then f − 2ei ∈ factor(G), but if f − 2ei , f ∈ factor(G), then possibly f − ki ei 6∈ factor(G). Thus, the ‘strongest’ form of the theorem is to take ki = 2 for i = 2, 3, . . . , p. There is a convexity motivation. Increase the hypotheses to fi ∈ factor(G − E(H)) and k1 ≥ kP i for i = 1, 2, . . . , p. Let dH (i) = ci with c = (c1 , c2 , . . . , cp , 0, 0, · · ·) so that pi=1 ci = k1 (we can delete edges from H if necessary). Now let p X ci C= and then take ai = ci /(ki C) so that Pp i=1 i=1 ai f0 = p X (3.1) ki = 1. Then if we take (3.2) ai fi , i=1 we get f 0 ∈ fract(G − E(H)). Since k1 ≥ ki , we have C ≥ 1, so Then, because f = f 0 + C1 c, we get f ∈ fract(G). 1 Cc ∈ fract(H). Corollary 3.1 [7]. Let G be a graph and k an even number. Let u0 , u1 , . . . , uk/2 be distinct vertices of G such that u1 , u2 , . . . , uk/2 ∈ NG (u0 ). If f (u0 ) = k and f ∈ factor(G − ui ) for i = 0, 1, . . . , k/2, then f ∈ factor(G). Proof. If f − f (ui )eui ∈ factor(G), then f (ui ) is even. We take H to be the star consisting of the k/2 edges (u0 , ui ) for i = 1, 2, . . . , k/2, so that G − E(H) is a subgraph of G − u0 . We can strengthen the above result in various ways, as follows, for example. Corollary 3.2. Let G be a graph with u0 , u1 , . . . , up being distinct vertices of G with f (u0 ) even. Assume G[{u0 , u1 , . . . , up }] has a subgraph H such that 154 JOURNAL OF GRAPH THEORY 2|E(H)| ≥ f (u0 ). If f ∈ factor((G − E(H)) − u0 ) and f ∈ factor(G − ui ) for i = 1, 2, . . . , p, then f ∈ factor(G). Corollary 3.3 [4]. Let G be a graph with U ⊆ V. Assume for some selected w ∈ U that f (w) is even and f (w) ≤ 2dG[U ] (w). If f ∈ factor(G − u) for each u ∈ U, then f ∈ factor(G). Proof. Let U = {1, 2, . . . , p} with 1 = w and let H consist of the edges of G[U ] incident with w. We note that f (u) is even for u ∈ U , since f − f (u)eu is an even grid point. One can get theorems dropping f by an odd amount in a coordinate, but then you must drop f by an odd amount in some other coordinate. The following result has its hypotheses chosen to strengthen a result of Katerinis and stay in the spirit of Theorem 3.1. Theorem 3.2. Let G be a graph so that vertex 1 has among its neighbors vertices 2, 3, . . . , p. Let ki be a positive integer for i = 1, 2, . . . , p with k1 ≥ k2 ≥ · · · ≥ kp and all ki ’s of the same parity. Let G[{1, 2, . . . , p}] have a P subgraph H containing the edges (1, i) for i = 2, 3, . . . , p where dH (1) ≥ k1 , pi=2 dH (i) ≥ kp and dH (p) ≤ kp . Define fi,j = f − ki ei − kj ej . Assume f1,i ∈ factor(G − E(H)) for i = 2, 3, . . . , p − 1 and fi,i+1 ∈ factor(G − (1, i)) for i = 2, 3, . . . , p − 1. Then f ∈ factor(G). Proof. Assume f 6∈ factor(G) and let S, T be a pair for which (1.6) is violated. Assume all the ki ’s are odd. With fi,i+1 ∈ factor(G) and ki ≥ ki+1 , we deduce that i 6∈ S . Thus, p is the only possible member of S ∩ {1, 2, . . . , p} (and only if kp−1 > kp ). Also 1 6∈ S . Now f1,j ∈ factor(G) forces either 1 ∈ T or j ∈ T or both, or both 1, j are in different odd components with respect to f (by Theorem 1.5). The latter case is impossible, because the edge (1, j) forces 1, j to be in the same component. Thus, if 1 6∈ T , then we get i ∈ T for i = 2, 3, . . . , p. Now consider replacing f, G by f1,p , G − E(H) in (1.6). Hence, λ(S, T ) is unchanged. P P Also t∈T dG (t) − dG−E(H) (t) ≥ kp , t∈T f (t) − f1,p (t) = kp and h(S, T ) decreases by at most 1, if 1 is in an odd component. We deduce (using Theorem 1.5) that f1,p 6∈ factor(G − E(H)), a contradiction. We may now assume 1 ∈ T . Now if i, i + 1 6∈ T , then consider replacing f, G by f , G − (1, i) in (1.6). From above, i 6∈ S and so λ(S, T ) is unaffected and P i,i+1 f (s) − fi,i+1 (s) ≥ 0. Also h(S, T ) decreases by at most 1 since, if i, i + 1 s∈S are in different components of G[V − (S ∪ T )], then the parity of the component containing i is unaffected (ki is odd but the deleted edge (1, i) has 1 ∈ T ). We note P t∈T dG (t) − dG−(1,i) (t) = 1. Hence, fi,i+1 6∈ factor(G − (1, i)). Thus, either i ∈ T or i + 1 ∈ T or both. If i 6∈ T for some i ∈ {2, 3, . . . , p}, consider replacing f, G by f1,i , G − E(H) in (1.6). We find that |{2, 3, . . . , p} − T | ≤ |T ∩ {2, 3, . . . , p}| + 1, and so h(S, T ) decreases by at most |T ∩ {2, 3, . . . , p}| + 1. Also, considering the edges (1, j) CONVEXITY OF DEGREE SEQUENCES 155 in H , X dH (t) ≥ k1 + |T ∩ {2, 3, . . . , p}|. (3.3) t∈T If i 6∈ S , then λ(S, T ) is unaffected, and so f1,i 6∈ factor(G − E(H)), a contradiction. P If i ∈ S , then i = p and we have that λ(S, T ) decreases by at most dH (p), but then s∈S f (s) − f1,p (s) = kp ≥ dH (p). As before, f1,p 6∈ factor(G − E(H)), a contradiction. p} ⊆ T . Consider replacing f, G by Now we can conclude that {1, 2, . . . ,P fP1,p , G − E(H) in (1.6). We compute t∈T f (t) − f1,p (t) = k1 + kp . Also t∈T dH (t) ≥ k1 + kp . We see that h(S, T ), λ(S, T ) are unchanged, and so f1,p 6∈ factor(G − E(H)), a contradiction. Having exhausted the cases, we conclude that f ∈ factor(G). If all the ki ’s are even, essentially the same argument works. One difference is that when i, i + 1 6∈ T and i, i + 1 are in different components of G[V − (S ∪ T )], then the parity of the component containing i + 1 is unchanged. A simple example of such a subgraph H is the star (1, 2), (1, 3), . . . , (1, k1 + 1) with p = k1 + 1. Corollary 3.4 [7]. Let G be a graph and k an odd number. Let u0 , u1 , . . . , uk be distinct vertices of G such that u1 , u2 , . . . , uk ∈ NG (u0 ). If f (u0 ) = k and f (ui ) ≤ k for i = 1, 2, . . . , k and f ∈ factor(G − {ui , uj }) for all pairs i, j with 0 ≤ i < j ≤ k, then f ∈ factor(G). Proof. Since f (u0 ) is odd and f − f (u0 )eu0 − f (ui )eui ∈ factor(G), f (ui ) is odd for i = 1, 2, . . . , k and we may reorder so that f (u0 ) ≥ f (u1 ) ≥ · · · ≥ f (uk ). Now take H to be the star consisting of the k edges (u0 , ui ) for i = 1, 2, . . . , k. Note that we have, in fact, strengthened the result of Katerinis, since we need only consider 2k − 1 pairs ui , uj . Consider being given positive integers ki for i = 1, 2, . . . , p all of the same parity. Then you could define for any I ⊆ {1, 2, . . . , p} fI = f − X ki ei . i∈I Consider cases where fI ∈ factor(G − EI ) for various I, EI with |I| = q , and EI ⊆ G[{1, 2, . . . , p}] (note that q must be even if all ki ’s are odd). Theorems can be obtained in the spirit of Theorem 3 in [4] using induction on q . Note that for q = 2 the following result appears weaker than Theorem 3.2. Theorem 3.3. Let {1, 2, . . . , p} ⊆ V and let ki be even positive integers for i = 1, 2, . . . , p with k1 ≥ k2 ≥ · · · ≥ kp . Let q be given. Let Hi be edge disjoint subgraphs of G satisfying V (Hi ) ⊆ {i, i + 1, . . . , p} and 2|E(Hi )| ≥ ki for i = 1, 2, . . . , q. For each I ⊆ {1, 2, . . . , p} with |I| = q satisfying {1, 2, . . . , r} ⊆ I for some r, we assume fI ∈ factor(G − ∪ri=1 E(Hi )). Then f ∈ factor(G). Proof. Use induction on q , where Theorem 3.1 proves the case q = 1. Assume the result is true for q = d and consider the case q = d + 1. Consider an I 156 JOURNAL OF GRAPH THEORY with |I| = d and 1, 2, . . . , r ∈ I , but r + 1 6∈ I . By hypothesis, fI∪{r+1} ∈ r factor(G − ∪r+1 i=1 E(Hi )) and for j > r + 1, fI∪{j} ∈ factor(G − ∪i=1 E(Hi )). Then by Theorem 3.1 with G replaced by (G − ∪ri=1 E(Hi )) and {1, 2, . . . , p} replaced by {r + 1, r + 2, . . . , p}, we have fI ∈ factor(G − ∪ri=1 E(Hi )). Now we may apply induction and deduce f ∈ factor(G). Corollary 3.5 [4]. Let G be a simple graph, q a positive integer, and R an induced subgraph of G. Let f be a function on V (G) such that for some q vertices r of R, f (r) is even and f (r) ≤ 2dR (r) − 2(q − 1). If for each set Q of q vertices of R, f ∈ factor(G − Q), then f ∈ factor(G). Proof. Apply Theorem 3.3 with V (R) = {1, 2, . . . , p}. Since G is simple, we not with 1, 2, . . . , i − are able to select Hi as those edges of R incident with i but P 1. We note that f (u) is even for u ∈ V (R), since f − qi=1 f (i)ei is an even grid point. References [1] R. P. Anstee, Minimum vertex weighted deficiency of (g, f )-factors: A greedy algorithm. Discr App Math 44 (1993), 247–260. [2] R. P. Anstee, Dividing a graph by degrees. J Graph Theory, 23 (1996), 377–384. [3] A. Bouchet and W. H. Cunningham, Delta-matroids, jump systems, and bisubmodular polyhedra. SIAM J Disc Math 8 (1995), 17–32. [4] P. Fraisse, P. Hell, and D. G. Kirkpatrick, A note on f -factors in directed and undirected multigraphs. Graphs Combin 2 (1986), 61–66. [5] D. R. Fulkerson, A. J. Hoffman, and M. H. McAndrew, Some properties of graphs with multiple edges. Canad J Math 17 (1965), 166–177. [6] P. Hell, D. G. Kirkpatrick, J. Kratochvíl and I. Kříž, On restricted two-factors. SIAM J Disc Math 1 (1988), 472–484. [7] P. Katerinis, Some conditions for the existence of f -factors. J Graph Theory 9 (1985), 513–521. [8] L. Lovász, The membership problem in jump systems, preprint. [9] W. T. Tutte, The factors of graphs. Canad J Math 4 (1952), 314–328.

1/--страниц