On the enumeration of one-factorizations of complete graphs containing prescribed automorphism groups

Abstract

In this paper we use orderly algorithms to enumerate (perfect) one-factorizations of complete graphs, the automorphism groups of which contain certain prescribed subgroups. We showed that, for the complete graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K 12"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>12</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{K_{12}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , excluding those one-factorizations containing exactly one automorphism of six disjoint cycles of length two, there are precisely 56391 nonisomorphic one-factorizations of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K 12"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>12</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{K_{12}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with nontrivial automorphism groups. We also determined that there are precisely 21 perfect one-factorizations of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K 14"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>14</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{K_{14}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> that have nontrivial automorphism groups.