pith. sign in

arxiv: math/0511316 · v1 · submitted 2005-11-12 · 🧮 math.CO

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

classification 🧮 math.CO
keywords alphatimesperfectproductcartesiandenoteeigenvaluesgraphs
0
0 comments X
read the original 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 $G\times H$. 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\times T)=\prod (2+\alpha^2)$, where the product ranges over all eigenvalues $\alpha$ of $T$. Moreover, we prove that Pm$(C_4\times T)$ is always a square or double a square. 2. Let $T$ be a tree. Then Pm$(P_4\times T)=\prod (1+3\alpha^2+\alpha^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\times T)=\prod (2+\alpha^2),$ where the product ranges over all positive eigenvalues $\alpha$ of $T$. Moreover, we prove that Pm$(C_4\times T)=[{Pm}(P_3\times T)]^2$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.