The Number Of 1-Factors Of Generalized Petersen Graph P(N, K) And Related Researches

Lovasz and Plummer conjectured that the number of 1-factors of 2-edge-connected cubic graph G is exponential in 1970s. In this dissertation, we discuss the lower bound of the number of 1-factors of the generalized Petersen graph P(N, k) and the lower bound of the number of hamiltonian cycles of P(N,3). We show that both of them are exponential. More precisely, let k be odd, we relable the vertices of P(N, k) in the cases of (N, k)= 1 and (N, k)≠1. and then calculating the number of 1-factors of the new graphs in one of the cases. We find that the lower bound of the number of 1-factors of the generalized Petersen graph P(N, k) is exponential, which confirms that the conjecture is true in the case of such generalized Petersen graph.In addition, as the intersection of the hamiltonian cycle of P(N,3) (if it has one) and its outer cycle is a sequence of paths, the length of which can be corresponding to the partition of the integer N which meet relevant conditions. We get the lower bound of the number of the hamiltonian cycles of P(N,3).