An infinite family of graphs with a facile count of perfect matchings Academic Article uri icon


  • Given a graph G=(V,E), let the triangulation 3=( 3,3) of G be the graph obtained from G by supplementing each uvE with a new vertex w along with new edges uw and wv (while retaining uv). Let dv be the degree of a vertex vV and let G be a tree T. Then it is proved that the count of perfect matchings of the Cartesian product of 3 with K2 is given as the product of factors dv+1 over all vV. Also under favorable conditions, the degree sequence of 3,K2 is reconstructed via factorization of the number of its perfect matchings. Previously introduced degree product polynomials play a helpful role. 2013 Elsevier B.V. All rights reserved.

published proceedings


author list (cited authors)

  • Rosenfeld, V. R., & Klein, D. J.

citation count

  • 4

complete list of authors

  • Rosenfeld, Vladimir R||Klein, Douglas J

publication date

  • March 2014