An infinite family of graphs with a facile count of perfect matchings

abstract

• 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.

authors

• Klein, Douglas

published proceedings

• DISCRETE APPLIED MATHEMATICS

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

publisher

• Elsevier  Publisher

published in

• DISCRETE APPLIED MATHEMATICS  Journal

keywords

• Cartesian Product Of Graphs
• Degree Sequence
• Hosoya Index
• Immanant
• K-matching Perfect Matching
• Matching Polynomial
• Permanent Contracted Permanent

Digital Object Identifier (DOI)

• 10.1016/j.dam.2013.09.010

start page

• 210

end page

• 214

volume

• 166

URL

• http://dx.doi.org/10.1016/j.dam.2013.09.010