Coherent cyclic order of a digraph

A cyclic ordering of a directed graph is considered unchanged by rotations or swaps of consecutive nonadjacent vertices. A representative is coherent when every backward edge

v_{j} \to v_{i}

has a forward directed path from

v_{i}

v_{j}

. Equivalently every edge is on a directed circuit that winds exactly once around the order. The number of backward edges on a circuit is invariant under the allowed changes. Every nontrivial strongly connected directed graph admits such an order.

Table of contents
- Cyclic stability of a digraph order Coherent cyclic order of a digraph

Cyclic stability of a digraph order ( $α (C)$ )

 0  0

The cyclic stability is the largest size of an independent set appearing consecutively in a representative of a coherent cyclic order of a digraph. It is at most the ordinary independence number. A set with no forward path between its distinct vertices can be moved into a consecutive block by swapping nonadjacent vertices. Choose a representative minimizing the span of the set; a vertex in a gap can be moved left or right past the block, contradicting minimality unless there are no gaps.