On the Word-Representability of 5-Regular Circulant Graphs
摘要
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\} \;\left| \; |i - j| \bmod n \in \{r_1, r_2, \dots , r_k\} \right\} \right. , \) where \(0 < r_1 < r_2 < \dots < r_k < \frac{n}{2}\) . Recently, Kitaev and Pyatkin showed that every 4-regular circulant graph is word-representable. Also, Srinivasan and Hariharasubramanian studied word-representability of circulant graphs and obtained some 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 extend these investigations to 5-regular circulant graphs. 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.