(P,Q)-ODD DIGRAPHS

A digraph D is (p, q)-odd if and only if any subdivision of D contains a directed cycle of length different from p mod q. A characterization of (p, q)-odd digraphs analogous to the Seymour-Thomassen characteriz ation of (1, 2)-odd digraphs is provided. In order to obtain this char acterization we study the lattice generated by the directed cycles of a strongly connected digraph. We show that the sets of directed cycles obtained from an ear decomposition of the digraph in a natural way ar e bases of this lattice. A similar result does not hold for undirected graphs. However we construct, for each undirected 2-connected graph G , a set of cycles of G which form a basis of the lattice generated by the cycles of G. (C) 1996 John Wiley & Sons, Inc.