An infinite family of graphs with a facile count of perfect matchings
Additional Document Info
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.