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 ![](https://www.scirp.org/html/htmlimages\22-7401734x\b5743366-8dfe-474e-b446-13d27953d25b.png)
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 ![](https://www.scirp.org/html/htmlimages\22-7401734x\20e525aa-9fd2-4b59-a091-7cb0a51a73e9.png)
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
![](https://www.scirp.org/html/htmlimages\22-7401734x\3b037ec4-afd1-4aa0-851f-5e405eb7f4ab.png)
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
,
,
,
.
, ![](https://www.scirp.org/html/htmlimages\22-7401734x\1a5be234-2309-4db7-96f9-88223a506388.png)
, ![](https://www.scirp.org/html/htmlimages\22-7401734x\187a99b5-440e-453b-b4cd-a962803a2ffd.png)
, ![](https://www.scirp.org/html/htmlimages\22-7401734x\0480b489-464d-44ff-b92c-65033d988047.png)
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
.
![](https://www.scirp.org/html/htmlimages\22-7401734x\d0d3bb22-b3c2-45ed-ab78-6461553c98ed.png)
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
![](https://www.scirp.org/html/htmlimages\22-7401734x\f88a68c3-3fcd-43b6-a581-693843f19f08.png)
Let
and
, and we note that
![](https://www.scirp.org/html/htmlimages\22-7401734x\5488a750-2cdd-459e-90dd-97838dcee8bd.png)
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 ![](https://www.scirp.org/html/htmlimages\22-7401734x\7b42a97e-079f-407a-b58f-0c65e9bd45a8.png)
Suppose that there exists a vertex
such that
, then
and
satisfy
(1), which contradicts the choice of
, therefore
for all ![](https://www.scirp.org/html/htmlimages\22-7401734x\779ae7a2-9d79-4529-9d3b-97ca6b709762.png)
Now we define
and let
be a vertex such that
.
Note that
holds, we consider two cases.
Cases 1: ![](https://www.scirp.org/html/htmlimages\22-7401734x\22df093e-e420-47aa-bf94-03556e3e8640.png)
Note that
,
,
, and
.
By (1), we obtain
![](https://www.scirp.org/html/htmlimages\22-7401734x\17274f8b-e383-4bae-983a-fff428fe6a7f.png)
This is a contradiction.
Cases 2: ![](https://www.scirp.org/html/htmlimages\22-7401734x\547f918a-5845-4895-b260-88a09e795436.png)
It is clear that
, then we defined
and let
be a vertex such that
by the condition of Theorem 2, the following inequality holds:
![](https://www.scirp.org/html/htmlimages\22-7401734x\8d71e3ae-d72e-4c8e-b735-c1c7f6ae0999.png)
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
![](https://www.scirp.org/html/htmlimages\22-7401734x\cd5f7e6f-510f-4986-93a5-d110fa0636a7.png)
And further by (1)
.
Note that
and
, so we have
![](https://www.scirp.org/html/htmlimages\22-7401734x\f55204f9-950b-446a-bb4b-82618a913011.png)
and hence
(3)
By (2) (3) we have
(4)
Let ![](https://www.scirp.org/html/htmlimages\22-7401734x\229c410a-fca6-4c4e-ab6d-6766633065aa.png)
Let
, we have
, Note that
, it is easy to see that
is the minimum when
.
So we have
(5)
If
, by (5) we have ![](https://www.scirp.org/html/htmlimages\22-7401734x\2ede75a4-497b-407a-b132-76ae64b312fd.png)
This is a contradiction.
So we suppose
, and hence
. By (5) we have
![](https://www.scirp.org/html/htmlimages\22-7401734x\7cd878f4-a184-40b8-b7c4-de5dd1e241de.png)
This is a final contradiction. Therefore theorem 2 is proved.