Jordan blocks of directed graphs

Question

Let $G$ be a (possibly weighted) directed graph with $n$ vertices and let $P$ be its transition matrix. That is, $P = D^{-1}A$ where $A$ is the graph's adjacency matrix and $D$ is a diagonal matrix such that $D[i,i] = \sum_{j=1}^{n}A[i,j]$ (I assume $D[i,i] \neq 0$ for every $i$).

It is well-known that $P$ may not be diagonalizable, even for regular directed graphs. Let $P = VJV^{-1}$ be a Jordan canonical form and let $m$ be the size of the largest Jordan block.

My question is - are there known natural families of directed graphs for which $m$ is constant (that is, does not grow with $n$)?

Answer 1

I don't know if this is natural, but the following constructions give such families (but the first one only for n = (m+1)k, where m is the size of the largest Jordan block):

Cycle comb Take the directed circle graph on k-vertices. Attach on each of the vertices of the directed cycle a directed path of length m. Then the transition matrix of the digraph has k Jordan blocks of size m to the eigenvalue 0.

Cycle lollipop You could also take the directed circle and attach a directed path of length m to just one vertex. The transition matrix of this digraph has one Jordan block of size m to the eigenvalue 0.

Note that for these families the transition matrix and the adjacency matrix are equal, as D[i,i] = 1 for any i.