Mathematics – Combinatorics
Scientific paper
2005-11-12
Discrete Applied Mathematics, 154(2006), 145-157
Mathematics
Combinatorics
15 pages, 4 figures
Scientific paper
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$.
Yan Weigen
Zhang Fuji
No associations
LandOfFree
Enumeration of perfect matchings of a type of Cartesian products of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Enumeration of perfect matchings of a type of Cartesian products of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enumeration of perfect matchings of a type of Cartesian products of graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-408554