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)∈ E for each x=y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. We prove that a graph is representable if and only if it is k-representable for some k. Examples of non-representable graphs are found in this paper. Some Wide classes of graphs are proven to be 2- and 3-representable. Several open problems are stated.
No takes yet. Share an insight, caveat, or question.
Kitaev et al. (2008) studied this question.