## On the number of dissimilar pfaffian orientations of graphs

^{1}
, Campo Grande,
Brasil and University of Waterloo, Waterloo, Canada.

^{2}
, Campinas,
Brasil;lucchesi@ic.unicamp.br

^{3}
University of Waterloo, Waterloo,
Canada.

A subgraph *H* of a graph *G* is *conformal* if *G - V(H)* has a
perfect matching. An orientation *D* of *G* is *Pfaffian* if, for
every conformal even circuit *C*, the number of edges of *C* whose
directions in *D* agree with any prescribed sense of orientation of
*C* is odd. A graph is *Pfaffian* if it has a Pfaffian
orientation. Not every graph is Pfaffian. However, if *G* has a
Pfaffian orientation *D*, then the determinant of the adjacency matrix
of *D* is the square of the number of perfect matchings of *G*. (See
the book by Lovász and Plummer [*Matching Theory*.
Annals of Discrete Mathematics, vol. 9. Elsevier Science (1986), Chap. 8.]
A *matching covered graph* is a nontrivial connected graph in
which every edge is in some perfect matching. The study of Pfaffian
orientations of graphs can be naturally reduced to matching covered
graphs. The properties of matching covered graphs are thus helpful in
understanding Pfaffian orientations of graphs. For example, say that
two orientations of a graph are *similar* if one can be obtained
from the other by reversing the orientations of all the edges in a cut
of the graph. Using one of the theorems we proved in [M.H. de Carvalho, C.L. Lucchesi and U.S.R. Murty,
Optimal ear decompositions of matching covered graphs.
*J. Combinat. Theory B* **85** (2002) 59–93]
concerning optimal ear decompositions, we show that if a matching
covered graph is Pfaffian then the number of dissimilar Pfaffian
orientations of *G* is 2^{b(G)}, where *b(G)* is the number of
“bricks” of *G*. In particular, any two Pfaffian orientations of a
bipartite graph are similar. We deduce that the problem of
determining whether or not a graph is Pfaffian is as difficult as the
problem of determining whether or not a given orientation is Pfaffian,
a result first proved by Vazirani and Yanakakis
[Pfaffian orientation of graphs, 0,1 permanents, and even cycles in
digraphs.
*Discrete Appl. Math.* **25** (1989) 179–180].
We establish a simple property of minimal graphs without a Pfaffian
orientation and use it to give an alternative proof of the
characterization of Pfaffian bipartite graphs due to Little
[ A characterization of convertible *(0,1)*-matrices.
*J. Combinat. Theory B* **18** (1975) 187–208] .

Mathematics Subject Classification: 05C70

*© EDP Sciences, 2005*