close

Вход

Забыли?

вход по аккаунту

?

410

код для вставкиСкачать
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.
Документ
Категория
Без категории
Просмотров
2
Размер файла
127 Кб
Теги
410
1/--страниц
Пожаловаться на содержимое документа