Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs
type: Item
instance of: scholarly article
title: Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs
zbMATH Open document ID: 1180.05054
author: Feng-Gen Lin
author: Lianzhu Zhang
published in: The Electronic Journal of Combinatorics
publication date: 2009-07-08T00:00:00Z
full work available at URL: https://eudml.org/doc/117513
full work available at URL: v16i1r52.html
review text: Summary: The importance of Pfaffian orientations stems from the fact that if a graph \(G\) is Pfaffian, then the number of perfect matchings of \(G\) (as well as other related problems) can be computed in polynomial time. Although there are many equivalent conditions for the existence of a Pfaffian orientation of a graph, this property is not well-characterized. The problem is that no polynomial algorithm is known for checking whether or not a given orientation of a graph is Pfaffian. Similarly, we do not know whether this property of an undirected graph that it has a Pfaffian orientation is in NP. It is well known that the enumeration problem of perfect matchings for general graphs is NP-hard. L. Lovász pointed out that it makes sense not only to seek good upper and lower bounds of the number of perfect matchings for general graphs, but also to seek special classes for which the problem can be solved exactly. For a simple graph \(G\) and a cycle \(C_n\) with \(n\) vertices (or a path \(P_n\) with \(n\) vertices), we define \(C_n \times G\) (or \(P_n\times G\)) as the Cartesian product of graphs \(C_n (or P_n)\) and \(G\). In the present paper, we construct Pfaffian orientations of graphs \(C_4\times G\), \(P_4\times G\) and \(P_3\times G\), where \(G\) is a non bipartite graph with a unique cycle, and obtain the explicit formulas in terms of eigenvalues of the skew adjacency matrix of \(\overrightarrow{G}\) to enumerate their perfect matchings by Pfaffian approach, where \(\overrightarrow{G}\) is an arbitrary orientation of \(G\).
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C76
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 5576433
zbMATH Keywords: Pfaffian orientation
zbMATH Keywords: Pfaffian graph
zbMATH Keywords: number of perfect matchings
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5576433