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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.