The lower bound for the number of 1-factors in generalized Petersen graphs

Document Type : Research Paper

Authors

1 Department of Mathematics‎, ‎East China Normal University‎, ‎Shanghai‎, ‎200241‎, ‎P.R‎. ‎China

2 ‎Shanghai Key Laboratory of PMMP‎, ‎Shanghai‎, ‎200241‎, ‎P.R‎. ‎China.

3 School of Mathematics‎, ‎Physics and Statistics‎, ‎Shanghai University of Engineering Science‎, ‎Shanghai‎, ‎201620‎, ‎P.R‎. ‎China.

4 Department of Mathematics‎, ‎East China Normal University‎, ‎Shanghai‎, ‎200241‎, ‎P.R‎. ‎China.

Abstract

‎In this paper‎, ‎we investigate the number of 1-factors of a‎ ‎generalized Petersen graph $P(N,k)$ and get a lower bound for the‎ ‎number of 1-factors of $P(N,k)$ as $k$ is odd‎, ‎which shows that the‎ ‎number of 1-factors of $P(N,k)$ is exponential in this case and‎ ‎confirms a conjecture due to Lovász and Plummer (Ann‎. ‎New York Acad‎. ‎Sci‎. ‎576(2006)‎, ‎no‎. ‎1‎, ‎389-398).

Keywords

Main Subjects

References

J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Elsevier Science Publ. Co. New York, 1976.
L.M. Bregman, Certain properties of nonnegative matrices and their permanents, Dokl. Akad. Nauk SSSR 211 (1973) 27--30.
M. Chudnovsky and P. Seymour, Perfect matchings in planar cubic graphs, Combinatorica 32 (2012), no. 4, 403--424.
T. Doslic, Counting perfect matchings in n-extendable graphs, Discrete Math. 308 (2008), no. 11, 2297--2300.
S.H. Fan and H.L. Xie, Weak vertex-transitivity of generalized Petersen graphs, Math. Appl. 17 (2004), no. 2, 271--276.
P.W. Kasteleyn, The statistics of dimers on a lattice: 1. The number of dimer arrangements on a quadratic lattice, Physica 27 (2009), no. 12, 1209--1225.
L. Lovasz and M.D. Plummer, Some recent results on graph matching, in: Graph Theory and Its Applications: East and West (Jinan, 1986), pp. 389--398, Ann. New York Acad. Sci. 576, New York Acad. Sci. New York, 1989.
L. Lovasz, On the structure of factorizable graphs, Acta Math. Hungar. 23 (1972), no. 1, 179--195.
A. Schrijver and W.G. Valiant, On lower bounds for permanents, Indag. Math. (N.S.) 42 (1980), no. 4, 425--427.
L.G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979), no. 2, 189--201.
M. Voorhoeve, A lower bound for the permanents of certain (0,1)-matrices, Indag. Math. (N.S.) 41 (1979), no. 1, 83--86.
Q.R. Yu and G.Z. Liu, Graph Factors and Matching Extensions, Higher Education Press, Beijing; Springer-Verlag, Berlin, 2009.
Bulletin of the Iranian Mathematical Society
Volume 43, Issue 6
November 2017
Pages 1925-1937

Files

History

  • Receive Date: 20 April 2016
  • Revise Date: 24 November 2016
  • Accept Date: 30 November 2016

Share

How to cite

Statistics