Enumeration of perfect matchings of a type of Cartesian products of graphs

DOI10.1016/J.DAM.2005.07.001MaRDI QIDQ2581564zbMATH OpenOpenAlexFDO

Authors Weigen Yan, Fuji Zhang

Publication date 10 January 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0511316

zbMATH Keywords

adjacency matrixPfaffian orientation

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $G$ be a graph and let Pm$(G)$ denote the number of perfect matchings of $G$. We denote the path with $m$ vertices by $P_m$ and the Cartesian product of graphs $G$ and $H$ by $GimesH$. In this paper, as the continuance of our paper [19], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results: 1. Let $T$ be a tree and let $C_n$ denote the cycle with $n$ vertices. Then Pm$(C_{4}imesT)=prod(2+alph{a}^2)$, where the product ranges over all eigenvalues $alpha$ of $T$. Moreover, we prove that Pm$(C_{4}imesT)$ is always a square or double a square. 2. Let $T$ be a tree. Then Pm$(P_{4}imesT)=prod(1+3alph{a}^2+alph{a}^4)$, where the product ranges over all non-negative eigenvalues $alpha$ of $T$. 3. Let $T$ be a tree with a perfect matching. Then Pm$(P_{3}imesT)=prod(2+alph{a}^2),$ where the product ranges over all positive eigenvalues $alpha$ of $T$. Moreover, we prove that Pm$(C_{4}imesT)=[Pm(P_{3}imesT){]}^2$.

Recommendations

• An infinite family of graphs with a facile count of perfect matchings
• Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs
• Enumeration of perfect matchings of the Cartesian products of graphs
• The enumeration of perfect matchings in two types of graphs
• scientific article; zbMATH DE number 5952364

Cites work

• scientific article; zbMATH DE number 1559555 (Why is no real title available?)
• scientific article; zbMATH DE number 2099352 (Why is no real title available?)
• scientific article; zbMATH DE number 1405497 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A characterization of convertible (0,1)-matrices
• A note on the number of perfect matchings of bipartite graphs
• Enumeration of perfect matchings in graphs with reflective symmetry
• Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians
• Even circuits of prescribed clockwise parity
• Matching theory
• On the number of Kekule structures of a type of oblate rectangles
• Perfect matchings and perfect squares
• Permanents, Pfaffian orientations, and even directed circuits
• Pólya's permanent problem

Cited in

(25)

• Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs
• An infinite family of graphs with a facile count of perfect matchings
• The enumeration of perfect matchings in two types of graphs
• The matching polynomials of hypergraphs and weighted hypergraphs
• On trees with perfect matchings
• Solving combinatorially the monomer-dimer problem on certain fractal scale-free lattices
• On the monomer-dimer problem of some graphs
• On the nullity and the matching number of unicyclic graphs
• Using edge generating function to solve monomer-dimer problem
• The characteristic polynomial and the matchings polynomial of a weighted oriented graph
• The Pfaffian property of Cayley graphs on dihedral groups
• Replacing Pfaffians and applications
• Enumerating spanning trees of graphs with an involution
• The Pfaffian property of circulant graphs
• Perfect matchings on a type of lattices with toroidal boundary
• On the rank of a real skew symmetric matrix described by an oriented graph
• On the skew spectra of Cartesian products of graphs
• Graphs isomorphic to their maximum matching graphs
• Construction of k-matchings in graph products
• A conjecture of Norine and Thomas for abelian Cayley graphs
• scientific article; zbMATH DE number 2099352 (Why is no real title available?)
• Pfaffian orientations and perfect matchings of scale-free networks
• Enumeration of perfect matchings of the Cartesian products of graphs
• The Pfaffian property of Cartesian products of graphs
• Maximum matchings in scale-free networks with identical degree distribution

This page was built for publication: Enumeration of perfect matchings of a type of Cartesian products of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581564)