Premium
( p,q )‐odd digraphs
Author(s) -
Galluccio Anna,
Loebl Martin
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199610)23:2<175::aid-jgt8>3.0.co;2-q
Subject(s) - digraph , combinatorics , mathematics , undirected graph , lattice (music) , characterization (materials science) , directed graph , strongly connected component , graph , discrete mathematics , subdivision , physics , materials science , archaeology , acoustics , history , nanotechnology
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 . © 1996 John Wiley & Sons, Inc.