The$$\ell$$-Rauzy Graphs on Infinite Words

Word-representable graphs are vital in the Combinatorics of Words and Graph Theory. We define one such graph, the $$ \ell $$ -Rauzy graph, and study its structural properties for a few infinite words. The $$ \ell $$ -Rauzy graph of order $$ k $$ for an infinite word $$ w $$ is a directed graph in which each vertex is a subword of length $$ k $$ of $$ w $$ , where any two vertices $$ u,v $$ form an arc $$ uv $$ iff the prefix of $$ v $$ of length $$ \ell $$ is the same as the suffix of $$ u $$ of length $$ \ell $$ and the concatenated word formed by the arc $$ uv $$ of length $$ 2k-\ell $$ is a subword of $$ w $$ . As main results, we show that the $$ \ell $$ -Rauzy graph of order $$ k $$ for the infinite Fibonacci word $$ f $$ is strongly connected, and we explicitly find the graph structure of the $$ \ell $$ -Rauzy graph of order $$ k $$ for an infinite periodic word, by knowing the locations of subwords of $$ f $$ and infinite periodic words. As locating the subwords in an infinite word is not easy, we show that the $$ \ell $$ -Rauzy graph of order $$ k $$ for an Arnoux-Rauzy word is strongly connected using a different approach. $$ \ell $$