Even circuits of prescribed clockwise parity (Q1422132)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Even circuits of prescribed clockwise parity
scientific article

    Statements

    Even circuits of prescribed clockwise parity (English)
    0 references
    0 references
    0 references
    5 February 2004
    0 references
    Summary: 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.
    0 references
    characterisation
    0 references
    signed graphs
    0 references
    Pfaffian graphs
    0 references
    perfect matchings
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references