A word-representable graph is a finite simple graph for which there is a finite word over its vertex
set, with each graph vertex appearing as a letter such that two distinct letters
alternate in the word precisely when the corresponding vertices are adjacent.
A representing word is 
-uniform if every graph vertex
occurs exactly 
times, where 
is a positive integer. The least such 
is the representation
number 
.
For example, the word 14213243 represents the cycle graph 
with edges 
, 
, 
, and 
. The corresponding subwords
obtained by retaining each edge's two letters are 1212,
1414, 2323, and 4343, which alternate. The remaining pairs
give 1133 and 4224, which do not alternate. Thus this is a 2-uniform
representation.
Akgün et al. (2019) enumerated the connected graphs that are not word-representable up to graph
isomorphism. For 
, 2, ..., their numbers begin 0, 0, 0, 0, 0, 1, 25, 929,
54957, 4880093, 650856040, ... (OEIS A290814).
A non-word-representable graph is minimal when every proper induced
subgraph is word-representable. For 
, 6, ..., the numbers of minimal examples begin 0, 1, 10,
47, 179, ... (OEIS A319491).
