Open AccessThe proof of the Perepechko’s conjecture concerning near-perfect matchings on Cm x Pn cylinders of odd order
Author(s) -
Rade Doroslovački,
Jelena Djokić,
Bojana Pantić,
Olga Bodroža-Pantić
Publication year - 2019
Publication title -
applicable analysis and discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.69
H-Index - 26
eISSN - 2406-100X
pISSN - 1452-8630
DOI - 10.2298/aadm181016002d
Subject(s) - mathematics , combinatorics , conjecture , sequence (biology) , graph , perfect power , order (exchange) , function (biology) , boundary (topology) , discrete mathematics , mathematical analysis , genetics , finance , evolutionary biology , economics , biology
For all odd values of m, we prove that the sequence of the numbers of near-perfect matchings on Cm x P2n+1 cylinder with a vacancy on the boundary obeys the same recurrence relation as the sequence of the numbers of perfect matchings on Cm x P2n. Further more, we prove that for all odd values of m denominator of the generating function for the total number of the near-perfect matchings on Cm x P2n+1 graph is always the square of denominator of generating function for the sequence of the numbers of perfect matchings on Cm x P2n graph, as recently conjectured by Perepechko.