ON THE NUMBER OF THE NON-EQUIVALENT KM-SPANNING SUBGRAPHS OF THE COMPLETE GRAPH WITH ORDER MK
Osamu Nakamura · Scientiae mathematicae Japonicae · 2003
Let m be greater than or equal to 2 and n be a multiple of m. We will call a spanning subgraph whose components are Km of the complete graph Kn a Km- spanning subgraph of Kn. The Dihedral group Dn acts on the complete graph Kn naturally. This action of Dn induces the action on the set of the Km-spanning sub- graphs of the complete graph Kn . In (3), we calculated the number of the equivalence classes of the 1-regular spanning subgraphs of the complete graph Kn of even order n by this action by using Burnside's Lemma. This is in the case m = 2. In this paper, we generalize this results and calculate the number of the non-equivalent Km-spanning subgraphs of Kn for all m and n. Let m be greater than or equal to 2 and let n be a multiple of m. Let fv0;v1;v2;¢¢¢ ;vni1g be the vertices of the complete graph Kn. The action to Kn of the Dihedral group Dn = f½0;½1;¢¢¢ ;½ni1;¾0;¾1;¢¢¢ ;¾ni1g is dened by