On the Word-Representability of 5-Regular Circulant Graphs

Abstract

A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that, for any two distinct vertices $x,y\in V$, $xy\in E$ if and only if $x$ and $y$ alternate in $w$. Two letters $x$ and $y$ are said to alternate in $w$ if, after removing all other letters from $w$, the resulting word is of the form $xyxy\dots$ or $yxyx\dots$ (of even or odd length). For a given set $R=\{r_1,r_2,\dots ,r_k\}$ of jump elements, an undirected circulant graph $C_n(R)$ on $n$ vertices has vertex set $\{0,1,\dots ,n-1\}$ and edge set $E=\left\{\{i,j\}||i-j|\mathrm{mod}n\in \{r_1,r_2,\dots ,r_k\}\right\},$ where $0<r_1<r_2<\cdots <r_k<\frac{n}{2}$. Recently, Kitaev and Pyatkin proved that every 4-regular circulant graph is word-representable. Srinivasan and Hariharasubramanian further investigated circulant graphs and obtained bounds on the representation number for $k$-regular circulant graphs with $2\le k\le 4$. In addition to these positive results, their work also presents examples of non-word-representable circulant graphs. In this work, we study word-representability and the representation number of 5-regular circulant graphs via techniques from elementary number theory and group theory, as well as graph coloring, graph factorization and morphisms.