Cycle rank

In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi (Eggan 1963). Intuitively, this concept measures how close a

digraph is to a directed acyclic graph (DAG), in the sense that a DAG has

cycle rank zero, while a complete digraph of order n with a self-loop at

each vertex has cycle rank n. The cycle rank of a directed graph is closely related to the tree-depth of an undirected graph and to the star height of a regular language. It has also found use

in sparse matrix computations (see Bodlaender et al. 1995) and logic

(Rossman 2008).

Definition

The cycle rank r(G) of a digraph G = (V, E) is inductively defined as follows:

If G is acyclic, then r(G) = 0.

If G is strongly connected and E is nonempty, then

r

(

G

)

=

1

+

min

v

∈

V

r

(

G

−

v

)

,

{\displaystyle r(G)=1+\min _{v\in V}r(G-v),\,}

where ⁠

G

−

v

{\displaystyle G-v}

⁠ is the digraph resulting from deletion of vertex v and all edges beginning or ending at v.

If G is not strongly connected, then r(G) is equal to the maximum cycle rank among all strongly connected components of G.

The tree-depth of an undirected graph has a very similar definition, using undirected connectivity and connected components in place of strong connectivity and strongly connected components.

History

Cycle rank was introduced by Eggan (1963) in the context of star height of regular languages. It was rediscovered by (Eisenstat & Liu 2005) as a generalization of undirected tree-depth, which had been developed beginning in the 1980s

and applied to sparse matrix computations (Schreiber 1982).