On a problem of walks (Q1296149)

The authors reformulate a conjecture on binary operations given by \textit{P. Tvrdík}, \textit{R. Harbane}, and \textit{M.-C. Heydemann} [Discrete Appl. Math. 83, No. 1-3, 279-301 (1998; Zbl 0902.68078)] in terms of coloured walks. This leads them to consider the problem of characterizing digraphs \(G\) such that the number \(W_k(G)\) of walks of length \(k\) in \(G\) is constant for all \(k\). They relate aspects of this problem to results on iterated line digraphs and show, for example, that the sequence \(\{W_k(G)\}\) is ultimately periodic if and only if the sequence \(\{L^k(G)\}\) of iterated line digraphs of \(G\) is ultimately periodic. They conclude with the problem of determining whether the sequence \(\{L^k(G)\}\) is ultimately a constant sequence when \(\{W_k(G)\}\) is a constant sequence.