Non-Word-Representable Single-Triangle Graphs with Word-Representable Line Graphs
Manuscript 17 October 2026 · Online 17 October 2026
Abstract
For every odd integer m >= 5, let G_m be the Mycielski graph of the cycle C_m with an additional edge joining the shadow copies of two adjacent cycle vertices. We prove that G_m is connected, has exactly one triangle, and is a minimal non-word-representable graph under induced-subgraph containment, while its line graph is word-representable. In fact, G_m is 4-vertex-critical. This gives connected examples of clique number three for a follow-up question of Mozhui, Dwary and Krishna. The smallest member of the family has eleven vertices and twenty-one edges. The proof combines a restriction lemma, a one-vertex extension of their explicit line-graph orientation, and a general vertex-criticality lemma for a single shadow-edge Mycielski extension.
Record
- Affiliation
- Mercury Software GmbH
- Contact
- [email protected] · GitHub
- Result
- Complete connected follow-up proof with induced minimality
- Categories
- math.CO
- Manuscript
- 17 October 2026
- Online release
- 17 October 2026
- Version
- 1.1
- License
- Creative Commons Attribution 4.0 International
Files and verification
The PDF is the canonical reading copy. The source archive contains the LaTeX manuscript, bibliography, reproducibility material, and audit documents without build artefacts.
Citation
Alper Ferudun, “Non-Word-Representable Single-Triangle Graphs with Word-Representable Line Graphs,” EulerSolve Research Papers, GRAPH-049, 2026. https://doi.org/10.5281/zenodo.23433839.
BibTeX
@misc{ferudun2026singletriangle,
author = {Ferudun, Alper},
title = {Non-Word-Representable Single-Triangle Graphs with Word-Representable Line Graphs},
year = {2026},
howpublished = {EulerSolve Research Papers},
url = {https://eulersolve.org/papers/graph-049/},
doi = {10.5281/zenodo.23433839},
note = {GRAPH-049; unrefereed preprint}
}