On a problem of walks

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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: On a problem of walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1296149)