eight=26.6  />, 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

  1. Y. Cui and M Cano, “Some Results on Odd Factors of Graphs,” Journal of Graph Theory, Vol. 12, No. 3, 1988, pp. 327-333. doi:10.1002/jgt.3190120305
  2. Z. Ryjáček, “On a Closure Concept in Claw-Free Graphs,” Journal of Combinatorial Theory, Series B, Vol. 70, No. 2, 1997, pp. 217-224.
  3. O. Favaron, “On n-Factor-Critical Graphs,” Discussiones Mathematicae Graph Theory, Vol. 16, 1996, pp. 41-51.
  4. N. Ananchuen and A. Daito, “Factor Criticality and Complete Closure of Graphs,” Discrete Mathematics, Vol. 265, No. 1-3, 2003, pp. 13-21.
  5. G. Z. Liu and Q. L. Yu, “Toughness and Perfect Matchings in Graphs,” Ars combinatorial, Vol. 48, 1998, pp. 129-134.
  6. C. P. Chen, “The Extendability of Matchings,” Journal of Beijing Agricultural Engineering University, Vol. 12, No. 4, 1992, pp. 36-39.
  7. C. Teng, “Some New Results on -Odd Factor of Graphs,” Journal of Shandong University, Vol. 31, No. 2, 1996, pp. 160-163.
  8. C. Teng, “Some New Results on -Odd Factor of Graphs,” Pure and Applied Mathematics, Vol. 10, 1994, pp. 188-192.
  9. D. P. Sumner, “Graphs with 1-Factors,” Proceedings of the American Mathematical Society, Vol. 42, No. 1, 1974, pp. 8-12.

Journal Menu >>