de Carvalho, Marcelo H., Lucchesi, Cláudio L., and Murty, U. S.R.. "On the number of dissimilar pfaffian orientations of graphs ." RAIRO - Theoretical Informatics and Applications 39.1 (2010): 93-113. <http://eudml.org/doc/92767>.
@article{deCarvalho2010,
abstract = {
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 B85 (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 2b(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 B18 (1975) 187–208] .
},
author = {de Carvalho, Marcelo H., Lucchesi, Cláudio L., Murty, U. S.R.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {perfect matching; Pfaffian graph; matching covered graphs},
language = {eng},
month = {3},
number = {1},
pages = {93-113},
publisher = {EDP Sciences},
title = {On the number of dissimilar pfaffian orientations of graphs },
url = {http://eudml.org/doc/92767},
volume = {39},
year = {2010},
}
TY - JOUR
AU - de Carvalho, Marcelo H.
AU - Lucchesi, Cláudio L.
AU - Murty, U. S.R.
TI - On the number of dissimilar pfaffian orientations of graphs
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 39
IS - 1
SP - 93
EP - 113
AB -
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 B85 (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 2b(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 B18 (1975) 187–208] .
LA - eng
KW - perfect matching; Pfaffian graph; matching covered graphs
UR - http://eudml.org/doc/92767
ER -
