Graphs with $1$-factors
HTML articles powered by AMS MathViewer
- by David P. Sumner PDF
- Proc. Amer. Math. Soc. 42 (1974), 8-12 Request permission
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
- Lowell W. Beineke and Michael D. Plummer, On the $1$-factors of a non-separable graph, J. Combinatorial Theory 2 (1967), 285–289. MR 210613
- Mehdi Behzad, A criterion for the planarity of the total graph of a graph, Proc. Cambridge Philos. Soc. 63 (1967), 679–681. MR 211896, DOI 10.1017/s0305004100041657
- Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911
- Julius Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891), no. 1, 193–220 (German). MR 1554815, DOI 10.1007/BF02392606
- W. T. Tutte, The factorization of linear graphs, J. London Math. Soc. 22 (1947), 107–111. MR 23048, DOI 10.1112/jlms/s1-22.2.107
Additional Information
- © Copyright 1974 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 42 (1974), 8-12
- MSC: Primary 05C99
- DOI: https://doi.org/10.1090/S0002-9939-1974-0323648-6
- MathSciNet review: 0323648