Geodesic
Even circuits of prescribed clockwise parity
The electronic journal of combinatorics, Tome 10 (2003)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We show that a graph has an orientation under which every circuit of even length is clockwise odd if and only if the graph contains no subgraph which is, after the contraction of at most one circuit of odd length, an even subdivision of $K_{2,3}$. In fact we give a more general characterisation of graphs that have an orientation under which every even circuit has a prescribed clockwise parity. Moreover we show that this characterisation has an equivalent analogue for signed graphs. We were motivated to study the original problem by our work on Pfaffian graphs, which are the graphs that have an orientation under which every alternating circuit is clockwise odd. Their significance is that they are precisely the graphs to which Kasteleyn's powerful method for enumerating perfect matchings may be applied.
DOI : 10.37236/1738
Classification : 05C38, 05C20, 05C22, 05C75
Mots-clés : characterisation, signed graphs, Pfaffian graphs, perfect matchings 
@article{10_37236_1738,
     author = {Ilse Fischer and C. H. C. Little},
     title = {Even circuits of prescribed clockwise parity},
     journal = {The electronic journal of combinatorics},
     year = {2003},
     volume = {10},
     doi = {10.37236/1738},
     zbl = {1031.05073},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1738/}
}
TY  - JOUR
AU  - Ilse Fischer
AU  - C. H. C. Little
TI  - Even circuits of prescribed clockwise parity
JO  - The electronic journal of combinatorics
PY  - 2003
VL  - 10
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1738/
DO  - 10.37236/1738
ID  - 10_37236_1738
ER  - 
%0 Journal Article
%A Ilse Fischer
%A C. H. C. Little
%T Even circuits of prescribed clockwise parity
%J The electronic journal of combinatorics
%D 2003
%V 10
%U http://geodesic.mathdoc.fr/articles/10.37236/1738/
%R 10.37236/1738
%F 10_37236_1738
Ilse Fischer; C. H. C. Little. Even circuits of prescribed clockwise parity. The electronic journal of combinatorics, Tome 10 (2003). doi: 10.37236/1738

Cité par Sources :