Solving computational problems in the theory of word-representable graphs

Akgün, Özgür and Gent, Ian and Kitaev, Sergey and Zantema, Hans (2019) Solving computational problems in the theory of word-representable graphs. Journal of Integer Sequences, 22 (2). pp. 1-18. 19.2.5. ISSN 1530-7638 (https://cs.uwaterloo.ca/journals/JIS/VOL22/Kitaev/...)

[thumbnail of Akgun-etal-JIS2019-Solving-computational-problems-in-the-theory-of-word-representable-graphs]
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 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.

ORCID iDs

Akgün, Özgür, Gent, Ian, Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Zantema, Hans;
  • Item type:Article
    ID code:67081
    Dates:
    Date
    Event
    24 February 2019
    Published
    24 February 2019
    Accepted
    Keywords:word-representable graph, semi-transitive orientation, representation number, enumeration, k-semi-transitive 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:03 Dec 2021 06:22
    URI:https://strathprints.strath.ac.uk/id/eprint/67081
CORE (COnnecting REpositories)