Word-representability of line graphs

Open Journal of Discrete Mathematics, Volume 1, Number 2 (2011)

Word graph A graph G=(V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x,y) is in E for each x not equal to y. The motivation to study representable graphs came from algebra, but this subject is interesting from graph theoretical, computer science, and combinatorics on words points of view. In this paper, we prove that for n greater than 3, the line graph of an n-wheel is non-representable. This not only provides a new construction of non-representable graphs, but also answers an open question on representability of the line graph of the 5-wheel, the minimal non-representable graph. Moreover, we show that for n greater than 4, the line graph of the complete graph is also non-representable. We then use these facts to prove that given a graph G which is not a cycle, a path or a claw graph, the graph obtained by taking the line graph of G k-times is guaranteed to be non-representable for k greater than 3.

Download the paper

Presentations

Additional material

DLT 2011 article

Later work (last updated 2 October 2026)

S. Kitaev and V. Lozin, Words and Graphs, Springer (2015). A monograph on word-representable graphs.
S. Kitaev and A. Pyatkin, Word-representable graphs: a survey, J. Appl. Ind. Math. 12 (2018). A survey of the theory of word-representable graphs.
S. Kitaev and A. Saito, On semi-transitive orientability of Kneser graphs and their complements, Discrete Math. 343 (2020). Uses the theorem that the line graph of $K_5$ is not word-representable: that line graph is the complement of the Kneser graph $K(5,2)$, which is therefore not semi-transitive.
M. M. Akbar, P. D. Akrobotu and C. P. Brewer, On the existence of word-representable line graphs of non-word-representable graphs, preprint (2021). Answers the first open question of this paper, whether the line graph of a non-word-representable graph is always non-word-representable, in the negative, with an example found by computer.
K. Mozhui, T. Dwary and K. V. Krishna, Line graphs of non-word-representable graphs are not always non-word-representable, preprint (2025). Answers the same question with an infinite family: the Mycielski graphs of odd cycles of length at least five are not word-representable, but their line graphs are.
K. Mozhui and K. V. Krishna, Word-representation of melon graphs, Graphs Combin. 42 (2026). Among other results, characterizes the melon graphs whose line graphs are word-representable, a step towards this paper’s question of which graphs have word-representable line graphs.
All citing papers on Google Scholar (31)