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 characterization of (1, 2)-odd digraphs is provided. In order to obtain this characterization 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 are 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.
(P,Q)-odd digraphs
Galluccio A;
1996
Abstract
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 characterization of (1, 2)-odd digraphs is provided. In order to obtain this characterization 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 are 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
