Cycle rank
| Relevant topics on |
| Graph connectivity |
|---|
The fourth has cycle rank 2; it is strongly connected, and it takes the removal of 1 vertex to make it not so. After that, each strongly connected component remaining has cycle rank 1, so the 1 vertex removed initially plus the max rank among the components. The fifth looks similar to the fourth, but since it is not strongly connected, and the maximum cycle rank of its components is 1, it has the same cycle rank as the second and third graphs.
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).