|Journal of Integer Sequences, Vol. 22 (2019), Article 19.2.5|
School of Computer and Information Sciences
University of Strathclyde
Glasgow, G1 1HX
Department of Computer Science
Eindhoven University of Technology
P. O. Box 513
5600 MB Eindhoven
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.
(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.