The multiplicity of 1-factors in the square of a graph. (English) Zbl 0545.05050

It is known that the square of each connected graph of even order has a 1-factor. The author shows that the square of any connected graph of order 2n has at least n 1-factors. Moreover, all the extremal graphs are described; they turn out to be special trees.
Reviewer: J.Širáň


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
Full Text: DOI


[1] , and , Graphs and Digraphs. Prindle, Weber and Schmidt, Boston (1979).
[2] Chartrand, Indag. Math. 35 pp 228– (1973)
[3] Nebesk, J. Graph Theory 2 pp 251– (1978)
[4] Sumner, Proc. Amer. Math. Soc. 42 pp 8– (1974)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.