The Parity of a Thicket

M. H. de Carvalho, C. H. C. Little

Abstract


A thicket in a graph $G$ is defined as a set of even circuits such that every edge lies in an even number of them. If $G$ is directed, then each circuit in the thicket has a well defined directed parity. The parity of the thicket is the sum of the parities of its members, and is independent of the orientation of $G$. We study the problem of determining the parity of a thicket $\mathcal{T}$ in terms of structural properties of $\mathcal{T}$. Specifically, we reduce the problem to studying the case where the underlying graph $G$ is cubic. In this case we solve the problem if $|\mathcal{T}| = 3$ or $G$ is bipartite. Some applications to the problem of characterising Pfaffian graphs are also considered.

Keywords


Graph theory; Pfaffian graphs; even directed circuits

Full Text: PDF