Non-flippable digraph without making directed 3-cycles

Masahiro Hachimori
Department of Systems Science,
Graduate School of Arts and Sciences,
University of Tokyo
3-8-1, Komaba, Meguro,
Tokyo 153-8902, Japan
Email : hachi@klee.c.u-tokyo.ac.jp

Jan 8, 1998 -- revised on May 30, 1999

Abstract:

We show the existence of a digraph without directed 3-cycles with the property that every flipping of the direction of one edge produces a directed 3-cycle. This is the first explicitly constructed example of graphs having this property. This construction is only based on a very trivial fact that if a flippable edge is identified with a non-flippable edge, then the edge becomes non-flippable, and after succesive identification, we finally make the flippable edges identified with non-flippable edges. I hope that the reader can understand how easily such graphs can be constructed.

This brief manuscript was originally written to be included into a paper which is no longer completed.