Solving computational problems in the theory of wordrepresentable graphs
Akgün, Özgür and Gent, Ian and Kitaev, Sergey and Zantema, Hans (2019) Solving computational problems in the theory of wordrepresentable graphs. Journal of Integer Sequences, 22 (2). pp. 118. 19.2.5. ISSN 15307638 (https://cs.uwaterloo.ca/journals/JIS/VOL22/Kitaev/...)
Preview 
Text.
Filename: Akgun_etal_JIS2019_Solving_computational_problems_in_the_theory_of_word_representable_graphs.pdf
Final Published Version Download (423kB) Preview 
Abstract
A simple graph G = (V, E) is wordrepresentable if there exists a word w over the alphabet V such that letters x and y alternate in w iff xy ∈ E. Wordrepresentable graphs generalize several important classes of graphs. A graph is wordrepresentable iff it admits a semitransitive orientation. We use semitransitive orientations to enumerate connected nonwordrepresentable 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 wordrepresentable iff it is krepresentable 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 krepresentable 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 ksemitransitive orientation refining the notion of a semitransitive orientation, and show computationally that the refinement is not equivalent to the original definition, unlike the equivalence of krepresentability and wordrepresentability.
ORCID iDs
Akgün, Özgür, Gent, Ian, Kitaev, Sergey ORCID: https://orcid.org/0000000333241647 and Zantema, Hans;

Item type: Article ID code: 67081 Dates: DateEvent24 February 2019Published24 February 2019AcceptedKeywords: wordrepresentable graph, semitransitive orientation, representation number, enumeration, ksemitransitive orientation, Electronic computers. Computer science, Computer Science(all) Subjects: Science > Mathematics > Electronic computers. Computer science Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 25 Feb 2019 14:12 Last modified: 25 May 2023 10:22 URI: https://strathprints.strath.ac.uk/id/eprint/67081