# Is arrangement-type graph on cyclic $k$-permutations of $n$ already studied?

The arrangement graph $$A_{n,k}$$ is the graph whose vertices are $$k$$-permutations of an $$n$$-vertex set $$X$$ (say, $$X=\mathbb{Z}_n$$) and two $$k$$-permutations are adjacent if they differ in exactly one position. For example, the graph $$A(4,2)$$ has vertex set $$\{(i,j)\ \colon\ i,j\in\mathbb{Z}_4,\ i\neq j\}$$ and there is an edge between $$(i,j)$$ and $$(k,l)$$ if and only if either (i) $$i=k$$ and $$j\neq l$$, or (ii) $$i\neq k$$ and $$j=l$$ [e.g.: (0,1) is adjacent to only (0,2), (0,3), (2,1) and (3,1)]. The graph $$A(4,2)$$ is isomorphic to the alternating graph $$AG_4$$, also called the cuboctahedron.

I wonder whether similar graphs exist in the literature whose vertices are cyclic $$k$$-permutations of an $$n$$-element set; let me denote this graph by $$CA_{n,k}$$ for 'cyclic arrangement graph'. Recall that a cyclic permutation can be written in a number of different ways. For instance, the cyclic permutation (1,2,3) may be written as (2,3,1) or (3,1,2); but, (1,3,2) is a different cyclic permutation. The graph $$CA(4,3)$$ has vertex set $$\{(i,j,k)\ \colon\ i,j,k\in\mathbb{Z}_4,\ i\neq j,\ j\neq k,\ k\neq i\}$$ and two cyclic permutations are adjacent if they differ in exactly one position in some representation of those cyclic permutations. E.g.: (0,1,2) is adjacent to only (0,1,3), (0,1,4), (0,3,2), (0,4,2), (3,1,2) and (4,1,2). So, (0,1,2) is adjacent to (1,2,3) because (1,2,3) can be written as (3,1,2).

In a way, these graphs are de-Brujin-type graphs whose vertices are cyclic $$k$$-length sequences of non-repeating symbols over an alphabet of $$n$$ symbols, and two vertices are adjacent if one vertex can be expressed as the other vertex by shifting all its symbols by one place to the left and adding a new symbol at the end.

• A correction/comment: These have more in common with overlap alphabet graphs found here than with de-Brujin graphs. Dec 18, 2021 at 6:13