Odd girth of line digraph.

Question

Are there any known results on the odd girth of the line digraph of a given digraph? By line digraph of a digraph $D$ having vertex set $V$ and arc set $A$, I mean the digraph whose vertex set is $A$ (the arc set of $D$), and whose arc set is the set of pairs of arcs of $D$ such that the head of the first equals the tail of the second. I.e., the set of pairs of the form $((u,v),(v,z))$ where both $(u,v)$ and $(v,z)$ are in $A$. The odd girth of a digraph is the length of the shortest (not necessarily directed) odd cycle in the digraph.

Answer 1

As you mentioned in comments, you want to find a digraph $G$ such that the iterated line operator is unbounded. Let $L(G)$ be the line digraph of $G$ and let the iterated line digraph be $$L^{(1)}(G)=L(G),\qquad \forall i>0,\ L^{(i+1)}(G)=L(L^{(i)}(G)).$$ Hence your problem is

Does there exist a digraph $G$ satisfying the following property. For all $g>0$, there exists $i>0$ such that $L^{(i)}(G)$ has odd-girth at least $g$.

For the sake of our problem, a graph with no cycle is said to have odd-girth $0$. The standard notation would be infinite odd-girth, making the problem trivial.

Fact 1. If a digraph $H$ contains a directed odd-cycle ${C_k}$, then $L(H)$ also contains ${C_k}$. Therefore, if $L^{(i)}(G)$ contains a directed odd-cycle ${C_k}$, then the odd-girth of $L^{(j)}(G)$ for any $j>i$ is at most $k$, a contradiction.

In order to get the desired property, you must have only undirected odd-cycles at each step in your graph. Let see what happens if you have one undirected cycle in your line digraph. Assume that $H$ is a digraph such that $L(H)\cong C_k$, with the cycle being not directed. Then there is at least one vertex $i$ with out-degree 2, and a vertex $j$ with in-degree 2. Then working-out the line operator backward, it's easy to see that $H$ is a actually an undirected $(k-2)$-cycle, with one pendent in-edge $i$, and one pendent out-edge $j$.

Now extending these pendent edge into directed paths, one can repeated the line process, each time reducing each path length by one, and increasing the cycle length by 2.

For example if $G$ is the following digraph

then its line digraph is

Therefore let $G_{2k+1}$ be a graph composed of a two internally vertex disjoint directed path, both with the same source $i$, and same end $j$, one of length $k$ and one of length $k+1$. Add a an infinite in-path on $i$, and an infinite out-path on j.

$G_{2k+1}$ has odd-girth $2k+1$, and $L(G)\cong G_{2k+3}$. Therefore creating an infinite sequence of digraph with strictly increasing odd girth, $$\forall i>0, \textrm{odd-girth}(L^{(i)}(G)) = 2k+1+2i.$$

If you restrict to finite graphs, then the process stops at one point and the odd girth jumps to $0$ because you reach a forest.