Representation Number 3 Classification

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G=(V,E)$ be a finite simple undirected graph. A word over $V$ is a finite sequence of vertices in which every vertex occurs. For distinct $x,y\in V$, let $w|_{\{x,y\}}$ be the word obtained by deleting every letter other than $x,y$. They alternate when this restriction has no equal consecutive letters, that is, it has the form $xyxy\cdots$ or $yxyx\cdots$, of either even or odd length. The word $w$ represents $G$ when, for every distinct $x,y$, \[ xy\in E\quad\Longleftrightarrow\quad x,y\text{ alternate in }w. \] Write $\mathrm{WR}(G)$ when such a word exists.

A word is $k$-uniform when every vertex occurs exactly $k$ times. For a word-representable graph its representation number is \[ \rho(G)=\min\{k\in\mathbb N:\text{some }k\text{-uniform word represents }G\}. \] Every word-representable graph admits a uniform representing word, so this minimum is defined. Uniform word length is $k|V|$; arbitrary repeated representing words are not used to measure the minimum.

Statement recorded in the supplied source.

Classify, up to isomorphism, all finite graphs in \[ \mathcal R_3=\{G:\rho(G)=3\}. \] Equivalently, give a structural necessary-and-sufficient criterion for existence of a $3$-uniform representing word and nonexistence of both $1$-uniform and $2$-uniform representing words. The classification is unrestricted by graph subclass. [S2]

Short English statement

Describe exactly the graphs that can be represented using three copies of every vertex but cannot be represented using one or two copies.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1434 (GRAPH-047). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Sergey Kitaev, On Graphs with Representation Number 3, arXiv:1403.1616v1 (2014), Sections 1--2, definition of R_k and uniform word representation. https://arxiv.org/pdf/1403.1616v1.