Graphs with -factors

Author:
David P. Sumner

Journal:
Proc. Amer. Math. Soc. **42** (1974), 8-12

MSC:
Primary 05C99

MathSciNet review:
0323648

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper it is shown that if *G* is a connected graph of order not containing a 1-factor, then for each *k*, , there exists an induced; connected subgraph of order 2*k* which also fails to possess a 1-factor. Several other sufficient conditions for a graph to contain a 1-factor are presented. In particular, it is seen that the connected even order line graphs and total graphs always contain a 1-factor.

**[1]**Lowell W. Beineke and Michael D. Plummer,*On the 1-factors of a non-separable graph*, J. Combinatorial Theory**2**(1967), 285–289. MR**0210613****[2]**Mehdi Behzad,*A criterion for the planarity of the total graph of a graph*, Proc. Cambridge Philos. Soc.**63**(1967), 679–681. MR**0211896****[3]**Frank Harary,*Graph theory*, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR**0256911****[4]**Julius Petersen,*Die Theorie der regulären graphs*, Acta Math.**15**(1891), no. 1, 193–220 (German). MR**1554815**, 10.1007/BF02392606**[5]**W. T. Tutte,*The factorization of linear graphs*, J. London Math. Soc.**22**(1947), 107–111. MR**0023048**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
05C99

Retrieve articles in all journals with MSC: 05C99

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9939-1974-0323648-6

Article copyright:
© Copyright 1974
American Mathematical Society