ABSTRACT

Let be a graph. If there exists a spanning subgraph such that, then is called to be -odd factor of. Some sufficient and necessary conditions are given for to have -odd factor where is any subset of such that.

1. Introduction

We consider finite undirected graph without loops and multiple edges .Let be a graph with vertex set and edge set Given, the set of vertexes adjacent to is said to be the neighborhood of, denoted by, and is called the degree of, If there exists a spanning subgraph such that, then is called a -odd factor of, especially, if for every such that, then it is called -odd factor. especially, -odd factor is 1-factor when n = 1. For a subset, let denote the subgraph obtained from by deleting all the vertexes of together with the edges incident with the vertexes of denotes the number of odd components of. The sufficient and necessary condition for graph to have -odd factor was given in paper [1] Ryjacek [2] introduced one kind of new closure operation: let be a graph, , if the subgraph induced by is not complete graph, we consider the following operation: jointing every pair of nonadjacent vertex in makes to be a complete graph. The operation is called local completely at point. If the subgraph induced by is k-vertex connected, then vertex is called local -vertex connected graph.

Favaron gave the concept of k-factor critical in paper [3]. If, and for any , is perfect matching ,then we call the graph to be k-factor critical. Of course, 0-factor critical graph is perfect matching. Favaron popularized a series of the properties of perfect matching to k-factor critical, at the same time the sufficient and necessary conditions were given for the graph to be k-factor critical, more results in factor critical graphs were referred to [4,5].

For -odd factor, Chen Ci-ping [6] gave a sufficient condition for a matching with exactly edges extended to -odd factor. Teng Cong generalized some results on kto -odd factor, and proved that the connected graph exists -odd factor with k-extended, then for the any edge of, exists-odd factor [7] with -extended. If there exists -odd factor of with k-extended, then there exists -odd factor with -extended, and is -connected [8]. We will popularize some results of k-factor critical to -odd factor, and gain several sufficient and necessary conditions for to have -odd factor for any subset of such that.

2. Main Results

We start with some lemmas as following.

Lemma 1 The sufficient and necessary condition for a graph to have -odd factor after cutting off any vertexes is

Proof For set with any vertexes, has -odd factor, next we will prove

For any and, let, where. Since has a -odd factor, by the sufficient and necessary condition for graph with -odd factor we have

.

Noting thatTherefore

For any and we have

the following that the set with any vertexes, has -odd factor, i.e., for any, there.

Noting that, of course.

By

and, we have

Lemma 2 [9] Connected claw free graphs of even order have 1-factor.

Lemma 3 Connected claw free graphs of even order have -odd factor.

Proof If, by lemma 2, the conclusion is proved. Assume that.

By contradiction, we assume that has no -odd factor, i.e., such that

.

then there exists such that connecting with three components of at least. If not, for, connects with two components of at most, consequently, contradiction.

Theorem 1 Let be graph with order, are a couple of nonadjacent vertexes and satisfy

then the sufficient and necessary condition for removing any vertexes with -odd factor is that getting rid of any vertexes with -odd factor.

Proof The necessary condition is obvious, next we prove the sufficient condition.

By contradiction, let remove any vertexes with -odd factor, but there exist vertexes after getting rid of the vertexes of without -odd factor. By lemma 1, there exists

such that

and

.

at the same time, by and

Thereby.

Furthermore, byConsequently

Accordingly

and

.

It shows that are part of two odd components of respectively.

Thus

.

On the other hand, by hypothesis

But

.

Contradiction.

Theorem 2 Let connected graph be order, are a couple of any nonadjacent vertexes of, and satisfy

then the sufficient and necessary condition for removing any vertexes with -odd factor is getting rid of  any vertexes with

-odd factor.

Proof is a spanning subgraph of, so the necessary condition is obvious.

Next we prove the sufficient condition. We suppose getting rid of any vertexes with - odd factor, but is not, i.e. there exist

such that

.

Be similar to the discussion of theorem 1

and

.

thereby are part of two odd components of respectively.

Noting that

(1)

By hypothesis

(2)

Combining (1) with (2)

Consequently

but.

Contradiction.

Theorem 3 Let be claw free graphs, be partial connection point. be graph obtained by locally fully on in point, then for, the sufficient and necessary condition for with -odd factor is with -odd factor.

Proof is a spanning subgraph of, so the necessary condition is obvious.

Next we prove the sufficient condition. Let have -odd factor, have no - odd factor. has -odd factor, , so.

On the other hand, is claw free, so is claw free.

By lemma 2, lemma 3, has two odd components at least.

If, let (is branch of). Now, has the same odd components as, therefore, has -odd factor. which is contradiction.

Next let, since has not odd components, for any odd components of,

is complete.

Let be adjacent vertexes of in two odd components of respectively.

Then is nonadjacent in the induced subgraph of

, which is contradiction to the fact that

is a locally connected vertex, since

The proof is complete.

REFERENCES