×

Counting near-perfect matchings on \(C_m \times C_n\) tori of odd order in the Maple system. (English. Russian original) Zbl 1459.05127

Program. Comput. Softw. 45, No. 2, 65-72 (2019); translation from Programmirovanie 45, No. 2, 49-57 (2019).
Summary: In the Maple computer algebra system, a set of recurrence relations and associated generating functions is derived for the number of near-perfect matchings on \({{C}_m} \times{{C}_n}\) tori of odd order at fixed values of the parameter \(m\) \((3 \leqslant m \leqslant 11)\). The identity of the recurrence relations for the number of perfect and near-perfect matchings is revealed for the same value of \(m\). An estimate for the number of near-perfect matchings is obtained at large odd \(m\) when \(n \to \infty \).

MSC:

05C30 Enumeration in graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68W30 Symbolic computation and algebraic computation
05A15 Exact enumeration problems, generating functions

Software:

Maple; OEIS
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Number of perfect matchings in the graph C_{11} X C_{2n}.

References:

[1] Valiant, L.G., The complexity of enumeration and reliability problems, SIAM J. Comput., 1979, vol. 8, no. 3, pp. 410-421. · Zbl 0419.68082 · doi:10.1137/0208032
[2] Björklund, A., Counting perfect matchings as fast as Ryser, Proc. SODA, 2012, pp. 914-921. · Zbl 1422.68103
[3] Perepechko, S.N., Number of perfect matchings in Cm × Cn graphs, Information Processes, 2016, vol. 16, no. 4, pp. 333-361.
[4] Petkovšek, M., Symbolic computation with sequences, Program. Comput. Software, 2006, vol. 32, no. 2, pp. 65-70. · Zbl 1103.68991 · doi:10.1134/S0361768806020022
[5] Kong, Y., Packing dimers on (2p + 1) × (2q + 1) lattices, Phys. Rev., 2006, vol. 016106.
[6] Klarner, D.A., Some remarks on the Cayley-Hamilton theorem, Amer. Math. Monthly, 1976, vol. 83, no. 5, pp. 367-369. · Zbl 0331.15004 · doi:10.1080/00029890.1976.11994127
[7] Wilf, H.S., A mechanical counting method and combinatorial applications, J. Comb. Theory, 1968, vol. 4, pp. 246-258. · Zbl 0162.03202 · doi:10.1016/S0021-9800(68)80006-7
[8] Voorhoeve, M., A lower bound for the permanent of certain (0, 1)-matrices, Indagationes Mathematicae, 1979, vol. 82, no. 1, pp. 83-86. · Zbl 0401.05005 · doi:10.1016/1385-7258(79)90012-X
[9] Karavaev, A.M. and Perepechko, S.N., Generating functions in the dimer problem on rectangular lattice graphs, Information Processes, 2013, vol. 13, no. 4, pp. 374-400.
[10] Malaschonok, G.I., Solution of systems of linear equations by the p-adic method, Program. Comput. Software, 2003, vol. 29, no. 2, pp. 59-71. · Zbl 1065.68117 · doi:10.1023/A:1022940530911
[11] Perepechko, S.N., Near-perfect matchings on cylinders Cm × Pn of odd order, EPJ Web Conf., 2018, vol. 02016.
[12] The on-line encyclopedia of integer sequences. http://www.oeis.org. · Zbl 1044.11108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.