On a problem of walks (Q1296149)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a problem of walks |
scientific article |
Statements
On a problem of walks (English)
0 references
12 July 1999
0 references
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.
0 references
semigroups
0 references
walks
0 references
iterated line digraphs
0 references