Journal of Integer Sequences, Vol. 22 (2019), Article 19.2.5

Solving Computational Problems in the Theory of Word-Representable Graphs

Özgür Akgün and Ian Gent
School of Computer Science
University of St Andrews
St Andrews, Fife KY16 9SX
United Kingdom

Sergey Kitaev
School of Computer and Information Sciences
University of Strathclyde
Glasgow, G1 1HX
United Kingdom

Hans Zantema
Department of Computer Science
Eindhoven University of Technology
P. O. Box 513
5600 MB Eindhoven
The Netherlands


A simple graph G = (V, E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w iff xy ∈ E. Word-representable graphs generalize several important classes of graphs. A graph is word-representable iff it admits a semi-transitive orientation. We use semi-transitive orientations to enumerate connected non-word-representable graphs up to the size of 11 vertices, which led to a correction of a published result. Obtaining the enumeration results took 3 CPU years of computation.

Also, a graph is word-representable iff it is k-representable for some k, that is, if it can be represented using k copies of each letter. The minimum such k for a given graph is called graph's representation number. Our computational results in this paper not only include distribution of k-representable graphs on at most 9 vertices, but also have relevance to a known conjecture on these graphs. In particular, we find a new graph on 9 vertices with high representation number. Also, we prove that a certain graph has highest representation number among all comparability graphs on odd number of vertices.

Finally, we introduce the notion of a k-semi-transitive orientation refining the notion of a semi-transitive orientation, and show computationally that the refinement is not equivalent to the original definition, unlike the equivalence of k-representability and word-representability.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A156808 A290814 A319489 A319490 A319491 A319492.)

Received October 1 2018; revised versions received February 22 2019; February 23 2019. Published in Journal of Integer Sequences, February 24 2019.

Return to Journal of Integer Sequences home page