Enumeration of perfect matchings of a type of Cartesian products of graphs
| dc.creator | Yan, Weigen | |
| dc.creator | Zhang, Fuji | |
| dc.date | 2005-11-12 | |
| dc.date.accessioned | 2026-07-07T06:51:10Z | |
| dc.date.available | 2026-07-07T06:51:10Z | |
| dc.description | 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+α^2)$, where the product ranges over all eigenvalues $α$ 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α^2+α^4)$, where the product ranges over all non-negative eigenvalues $α$ of $T$. 3. Let $T$ be a tree with a perfect matching. Then Pm$(P_3\times T)=\prod (2+α^2),$ where the product ranges over all positive eigenvalues $α$ of $T$. Moreover, we prove that Pm$(C_4\times T)=[{Pm}(P_3\times T)]^2$. | |
| dc.description | 15 pages, 4 figures | |
| dc.identifier | https://arxiv.org/abs/math/0511316 | |
| dc.identifier | http://arxiv.org/abs/math/0511316 | |
| dc.identifier | Discrete Applied Mathematics, 154(2006), 145-157 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/104898 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C70; 05C90 | |
| dc.title | Enumeration of perfect matchings of a type of Cartesian products of graphs | |
| dc.type | text |