Pushing the cycles out of directed graphs
by
Gary MacGillivray
Mathematics and Statistics, University of Victoria, Canada
Coauthors: Jing Huang (Mathematics and Statistics, University of Victoria, Canada), Anders Yeo (Computer Science, University of Aarhus, Denmark)

Let D be a directed graph. When a subset X of vertices of D is "pushed", the orientation of every arc with exactly one end in X is reversed. A considerable amount of attention has recently been devoted to questions concerning when the push operation can be used to transform a given directed graph into one with certain prescribed properties, e.g., strongly connected, hamiltonian, or acyclic. We will discuss results concerning which directed graphs can be rendered acyclic using the push operation, focussing on forbidden subdigraph characterisations for classes of well-structured digraphs including orientations of chordal graphs, and bipartite permutation digraphs.

Date received: April 19, 2001