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

DOI10.1016/J.DAM.2005.07.001zbMATH Open1083.05035arXivmath/0511316OpenAlexW2031024136MaRDI QIDQ2581564FDOQ2581564

Authors: Weigen Yan, Fuji Zhang 

Publication date: 10 January 2006

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

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

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

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

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)

Cites Work

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

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 matching polynomials of hypergraphs and weighted hypergraphs
• The enumeration of perfect matchings in two types of graphs
• Solving combinatorially the monomer-dimer problem on certain fractal scale-free lattices
• On trees with perfect matchings
• On the monomer-dimer problem of some graphs
• Using edge generating function to solve monomer-dimer problem
• On the nullity and the matching number of unicyclic graphs
• 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
• On the rank of a real skew symmetric matrix described by an oriented graph
• Perfect matchings on a type of lattices with toroidal boundary
• On the skew spectra of Cartesian products of graphs
• Construction of k-matchings in graph products
• Graphs isomorphic to their maximum matching graphs
• A conjecture of Norine and Thomas for abelian Cayley graphs
• Title not available (Why is that?)
• 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)