On semi-transitive orientability of circulant graphs

A graph $G = (V, E)$ is said to be word-representable if a word w can be formed using the letters of the alphabet V such that for every pair of vertices x and y, xy ∈ E if and only if x and y alternate in w. A semi-transitive orientation is an acyclic directed graph where for any directed path v₀ → v₁ → … → vₘ, m ≥ 2 either there is no arc between v₀ and vₘ or for all 1 ≤ i < j ≤ m there is an arc between vᵢ and vⱼ. An undirected graph is semi-transitive if it admits a semi-transitive orientation. For given positive integers n, a₁, a₂, …, aₖ, we consider the undirected circulant graph with set of vertices \0, 1, 2, …, n-1\ and the set of edges ~ | ~ (i - j) n or (j-i) n are in ₁, a₂, …, aₖ\\, where 0 < a₁ < a₂ < … < aₖ < (n+1)/2. Recently, Kitaev and Pyatkin have shown that every $4$-regular circulant graph is semi-transitive. Further, they have posed an open problem regarding the semi-transitive orientability of circulant graphs for which the elements of the set ₁, a₂, …, aₖ\ are consecutive positive integers. In this paper, we solve the problem mentioned above. In addition, we show that under certain assumptions, some k(≥5)-regular circulant graphs are semi-transitive, and some are not. Moreover, since a semi-transitive orientation is a characterisation of word-representability, we give some upper bound for the representation number of certain k-regular circulant graphs.