Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Graphs with $ 1$-factors

Author: David P. Sumner
Journal: Proc. Amer. Math. Soc. 42 (1974), 8-12
MSC: Primary 05C99
MathSciNet review: 0323648
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper it is shown that if G is a connected graph of order $ 2n(n > 1)$ not containing a 1-factor, then for each k, $ 1 < k \leqq n$, there exists an induced; connected subgraph of order 2k 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.

References [Enhancements On Off] (What's this?)

  • [1] L. W. Beineke and M. D. Plummer, On the 1-factors of a nonseparable graph, J. Combinatorial Theory 2 (1967), 285-289. MR 35 #1499. MR 0210613 (35:1499)
  • [2] M. Behzad, A criterion for the planarity of the total graph of a graph, Proc. Cambridge Philos. Soc. 63 (1967), 679-681. MR 35 #2771. MR 0211896 (35:2771)
  • [3] F. Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969. MR 41 #1566. MR 0256911 (41:1566)
  • [4] J. Petersen, Die Theorie der regulären Graphen, Acta Math. (1891), 193-220. MR 1554815
  • [5] W. T. Tutte, The factorizations of linear graphs, J. London Math. Soc. 22 (1947), 107-111. MR 9, 297. MR 0023048 (9:297d)

Similar Articles

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

Retrieve articles in all journals with MSC: 05C99

Additional Information

Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society