Enumeration of perfect matchings of the Cartesian products of graphs
type: Item
instance of: scholarly article
title: Enumeration of perfect matchings of the Cartesian products of graphs
DOI: 10.37236/11141
author: Wei Li
author: Yao Wang
published in: The Electronic Journal of Combinatorics
publication date: 2023-04-19T00:00:00Z
review text: Summary: A subgraph \(H\) of a graph \(G\) is nice if \(G-V(H)\) has a perfect matching. An even cycle \(C\) in an oriented graph is oddly oriented if for either choice of direction of traversal around \(C \), the number of edges of \(C\) directed along the traversal is odd. An orientation \(D\) of a graph \(G\) with an even number of vertices is Pfaffian if every nice cycle of \(G\) is oddly oriented in \(D \). Let \(P_n\) denote a path on \(n\) vertices. The Pfaffian graph \(G \times P_{2n}\) was determined by \textit{F. Lu} and \textit{L. Zhang} [J. Comb. Optim. 27, No. 3, 530--540 (2014; Zbl 1322.90078)]. In this paper, we characterize the Pfaffian graph \(G \times P_{2n+1}\) with respect to the forbidden subgraphs of \(G\). We first give sufficient and necessary conditions under which \(G\times P_{2n+1}\) \((n\geqslant 2)\) is Pfaffian. Then we characterize the Pfaffian graph \(G \times P_3\) when \(G\) is a bipartite graph, and we generalize this result to the case \(G\) contains exactly one odd cycle. Following these results, we enumerate the number of perfect matchings of the Pfaffian graph \(G \times P_n\) in terms of the eigenvalues of the orientation graph of \(G\), and we also count perfect matchings of some Pfaffian graph \(G \times P_n\) by the eigenvalues of \(G\).
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 7676077
zbMATH Keywords: Pfaffian graph
MaRDI profile type: MaRDI publication profile
full work available at URL: https://doi.org/10.37236/11141
OpenAlex ID: W4362699352
cites work: On the skew spectra of Cartesian products of graphs
cites work: Enumeration of perfect matchings of lattice graphs by Pfaffians
cites work: A characterisation of Pfaffian near bipartite graphs
cites work: Even circuits of prescribed clockwise parity
cites work: Statistical Mechanics of Dimers on a Plane Lattice
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Q5605168
cites work: Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs
cites work: A characterization of convertible (0,1)-matrices
cites work: Matching theory
cites work: The Pfaffian property of Cartesian products of graphs
cites work: Enumeration of perfect matchings of a type of quadratic lattice on the torus
cites work: Dimer statistics on the Möbius strip and the Klein bottle
cites work: Close-packed dimers on nonorientable surfaces
cites work: Minimally non-Pfaffian graphs
cites work: Pólya's permanent problem
cites work: Permanents, Pfaffian orientations, and even directed circuits
cites work: Dimer problem in statistical mechanics-an exact result
cites work: Q5491020
cites work: The complexity of computing the permanent
cites work: Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians
cites work: Enumeration of perfect matchings of a type of Cartesian products of graphs
Recommended article: Integral representations on supermanifolds: super Hodge duals, PCOs and Liouville forms
Recommended article: Hodge star as braided Fourier transform
Recommended article: The geometry of supermanifolds and new supersymmetric actions
Recommended article: Hodge dualities on supermanifolds
Recommended article: Q4352759
description: scientific article; zbMATH DE number 7676077