A Neighborhood Condition for Graphs to Have Special [a,b]-Factor ()
Keywords:Graph; Factor; [a,b]-Factor; The Minimum Degree; Neighborhood Condition
1. Introduction
We consider the finite undirected graph without loops and multiple edges. Let 
be a graph with vertex set 
and edge set 
Given
, the set of vertices adjacent to 
is said to be the neighborhood of
, denoted by
. 
is called the degree of 
and we write 
for
. Furthermore we define
,
.
For a subset
, let 
denote the subgraph obtained from 
by deleting all the vertices of 
together with the edges incident with the vertices of
.
Let 
and 
be integers such that
. A 
factor of 
is defined as a spanning subgraph 
of 
such that 
for all
. Other notations and terminology are the same as those in [1]
The existence of a factor for a graph G is closely related to the degree of vertices. Concerning the minimum degree and the existence of k-factor Egawa, Enomoto [2] and Katerinis [3] proved that there exists k factor when
and 
for a graph
. Iida and Nishimura [4] proved that if 
and 
there exists k-factor for a graph
.
H. Y. Pan [5] generalized the result of Iida and Nishimura to [a, b] -factor: if 
and
, 
has an 
-factor.
Concerning adjacent set union and 
-factor, in 2000 H. Matsuda gave the following result:
Theorem 1 [5]: Let a, b be integer such that
, and G be a graph of order 
with 
and
.
If 
for any two non-adjacent vertices 
and 
of
, then 
has a 
factor We prove the following theorem for a graph to have a 
factor with given properties, which is an extension of theorem 1.
Theorem 2: Let 
and 
be integers such that
, 
be a graph of order
, and 
be a subgraph of G with 
edges. If
, and 
for any two non-adjacent vertices 
and 
of
, when
, we suppose
Then 
has a 
factor containing all edges of
.
2. Proof of Theorem 2
Let S and T be two disjoint subset of V(G), E1 and E2 be two disjoint subset of E(G). Let
,
, 
,
.
, 
, 
, 
Lemma 1 [6]: Let 
be a graph, and let 
and 
be two integer-valued functions defined on 
such that 
for all
. Let 
and 
be two disjoint subsets of
.
Then 
has a 
-factor 
such that 
and 
if and only if for any two disjoint subsets 
and 
of
.
Lemma 2: Let 
and 
be integers such that
, and 
be a graph, and 
be a subgraph of
. Then 
has a 
factor 
such that 
if and only if
Let 
and
, and we note that
where 
and
.
It is easy to see Lemma 2 is an immediately result of Lemma 1.
Now we prove Theorem 2: Suppose that 
satisfies the assumptions of Theorem 2, but it has no 
factor as described in Theorem 2. Then by Lemma 2 there exist two disjoint subsets 
and 
of 
such that
(1)
We choose such S and 
so that 
is minimum. If
, then by (1) we get
which is a contradiction. Since 
for all
, hence we have 
Suppose that there exists a vertex 
such that
, then 
and 
satisfy
(1), which contradicts the choice of
, therefore 
for all 
Now we define
and let 
be a vertex such that
.
Note that 
holds, we consider two cases.
Cases 1: 
Note that
, 
,
, and
.
By (1), we obtain
This is a contradiction.
Cases 2: 
It is clear that
, then we defined 
and let
be a vertex such that 
by the condition of Theorem 2, the following inequality holds:
which implies
(2)
Note that the number of vertices in 
which satisfies the equality 
is at most
, and the rest of vertices in 
satisfy
.
So we obtain
And further by (1)
.
Note that 
and
, so we have
and hence
(3)
By (2) (3) we have
(4)
Let 
Let
, we have
, Note that
, it is easy to see that 
is the minimum when
.
So we have
(5)
If
, by (5) we have 
This is a contradiction.
So we suppose
, and hence
. By (5) we have
This is a final contradiction. Therefore theorem 2 is proved.