The Lower Bound Of The Number Of 1-Factors Of Generalized Petersen Graph P(N,3)

In this paper, we study a conjecture of Lovasz and Plummer which states that the lower bound of the number of 1-factors of 2-edge-connected cubic graph G is exponential. We estimate the number of 1-factors of the generalized Petersen graph P(N, 3) is exponential and show that the lower bound of the number of 1-factors of P(N, 3) is exponential.A generalized Petersen graph P(N, 3) is the graph which has vertex set V(G)= {ui,wi|i=1,2,…,N}, and edge set E(G)={uiui+1,wiwi+3, uiwi|i=1,2,…,N}. In this paper, we construct an isomorphic graph H (V(H)={ui, vj|i=1, 2,…, N, j= 0, 1, 2,…, N-1}, E0={viu[3i+1]|i=0, 1,…, N-1}) of P(N, 3), and use the com-binatoric methods to find that the lower bound of number of 1-factors of General-ized Petersen Graph P(N, 3) is exponential. More precisely, when N≠3k (k∈N+), H-E0 is the Union of two cycles, in this case, we can get an exponential lower bound N/(?) (α2[N/6]-β2[N/6]), (where [N/6] is the biggest integer which is not more than N/6); When N = 3k (k∈N+), H-E0 is the union of four cycles, we have got the num-ber of 1-factors of G=P(N, 3) in some cases, when N=6n, the lower bound is 12/(?)(αN/3-βN/3) and when N=6n+3, the lower bound is 4N+1/(?)(α(N-6)/3-β(N-6)/3), whereα=(1+(?))/2,β=(1-(?))/2.