ABSTRACT

Let G be a graph of order n, and let a and b be integers, such that 1 ≤ a < b. Let H be a subgraph of G with m(≤b) edges, and δ(G) be the minimum degree. We prove that G has a [a,b]-factor containing all edges of H if, , and when a ≤ 2,.

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), E₁ and E₂ 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 getwhich 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.

REFERENCES