Back to Search
Start Over
Enumeration of perfect matchings of a type of Cartesian products of graphs
- Source :
- Discrete Applied Mathematics. 154(1):145-157
- Publication Year :
- 2006
- Publisher :
- Elsevier BV, 2006.
-
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$.<br />Comment: 15 pages, 4 figures
- Subjects :
- 05C70
05C90
Pfaffian orientation
Pfaffian
Combinatorics
symbols.namesake
Nice cycle
Reflection symmetry
Skew adjacency matrix
Enumeration
FOS: Mathematics
Cartesian product
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Perfect matching
Eigenvalues and eigenvectors
Mathematics
Discrete mathematics
Bipartite graph
Cartesian product of graphs
Mathematics::Combinatorics
Applied Mathematics
Graph
symbols
Combinatorics (math.CO)
Subjects
Details
- ISSN :
- 0166218X
- Volume :
- 154
- Issue :
- 1
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi.dedup.....d015a4e186681d76ce8738393eb08945
- Full Text :
- https://doi.org/10.1016/j.dam.2005.07.001