Abstract:A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and only if $xy\in E$. For integers $n>k>0 $, the shift graph $G(n,k)$ is the graph whose vertex set consists of all increasing $k$-tuples $(x_1,x_2,\dots,x_k)$ with $1\le x_1<x_2<\cdots<x_k\le n$, where two vertices $(x_1,\dots,x_k)$ and $(y_1,\dots,y_k)$ are adjacent whenever $x_{i+1}=y_i$ for all $1\le i\le k-1$ or $y_{i+1}=x_i$ for all $1\le i\le k-1$. Shift graphs are classical examples of sparse graphs having arbitrarily high chromatic number and odd girth. We further observe that shift graphs arise naturally as induced subgraphs of simplified de Bruijn graphs. Although simplified de Bruijn graphs contain non-word-representable members in general, we prove that the entire class of shift graphs is word-representable. We also introduce a natural generalization of shift graphs in which adjacency is defined by more than one shift condition, and show that these generalized shift graphs are likewise word-representable. As a consequence, we obtain an explicit family of graphs exhibiting a contrast between line graph and line digraph constructions: there exists a family of word-representable graphs whose line graphs are not word-representable when the number of vertices is at least $5$, while their line digraphs are word-representable.
| Subjects: | Combinatorics (math.CO); Discrete Mathematics (cs.DM) |
| Cite as: | arXiv:2605.02268 [math.CO] |
| (or arXiv:2605.02268v2 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.02268 arXiv-issued DOI via DataCite |
From: Ramesh Hariharasubramanian [view email]
[v1]
Mon, 4 May 2026 06:21:59 UTC (10 KB)
[v2]
Fri, 22 May 2026 11:05:19 UTC (10 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。