2024/06/05 by Eshwar Srinivasan, Srinivasan, Eshwar, Ramesh Hariharasubramanian +1 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Mathematics and Applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2406.03168
openalex publication_date 2024/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 v0 → v1 → … → vm, m ≥ 2 either there is no arc between v0 and vm or for all 1 ≤ i < j ≤ m there is an arc between vi and vj. An undirected graph is semi-transitive if it admits a semi-transitive orientation. For given positive integers n, a1, a2, …, ak, we consider the undirected circulant graph with set of vertices \0, 1, 2, …, n-1\ and the set of edges\ij ~ | ~ (i - j) \pmod n or (j-i) \pmod n are in \a1, a2, …, ak\\, where 0 < a1 < a2 < … < ak < (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 \a1, a2, …, ak\ 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.