Solving computational problems in the theory of word-representable graphs

Özgür Akgün, Ian Gent, Sergey Kitaev, Hans Zantema

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Uittreksel

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.
TaalEngels
Artikelnummer19.2.5
Aantal pagina's18
TijdschriftJournal of Integer Sequences
Volume22
Nummer van het tijdschrift2
StatusGepubliceerd - 2019

Vingerafdruk

Graph in graph theory
Representability
Comparability Graph
Graph Representation
Odd number
Simple Graph
Alternate
Enumeration
Computational Results
Refinement
Equivalence
Generalise

Trefwoorden

    Citeer dit

    Akgün, Özgür ; Gent, Ian ; Kitaev, Sergey ; Zantema, Hans. / Solving computational problems in the theory of word-representable graphs. In: Journal of Integer Sequences. 2019 ; Vol. 22, Nr. 2.
    @article{33890141ab954e7ab8b4976b9ce02593,
    title = "Solving computational problems in the theory of word-representable graphs",
    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.",
    keywords = "Enumeration, K-semi-transitive orientation, Representation number, Semi-transitive orientation, Word-representable graph",
    author = "{\"O}zg{\"u}r Akg{\"u}n and Ian Gent and Sergey Kitaev and Hans Zantema",
    year = "2019",
    language = "English",
    volume = "22",
    journal = "Journal of Integer Sequences",
    issn = "1530-7638",
    publisher = "University of Waterloo",
    number = "2",

    }

    Solving computational problems in the theory of word-representable graphs. / Akgün, Özgür; Gent, Ian; Kitaev, Sergey; Zantema, Hans.

    In: Journal of Integer Sequences, Vol. 22, Nr. 2, 19.2.5, 2019.

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    TY - JOUR

    T1 - Solving computational problems in the theory of word-representable graphs

    AU - Akgün,Özgür

    AU - Gent,Ian

    AU - Kitaev,Sergey

    AU - Zantema,Hans

    PY - 2019

    Y1 - 2019

    N2 - 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.

    AB - 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.

    KW - Enumeration

    KW - K-semi-transitive orientation

    KW - Representation number

    KW - Semi-transitive orientation

    KW - Word-representable graph

    UR - http://www.scopus.com/inward/record.url?scp=85063988925&partnerID=8YFLogxK

    M3 - Article

    VL - 22

    JO - Journal of Integer Sequences

    T2 - Journal of Integer Sequences

    JF - Journal of Integer Sequences

    SN - 1530-7638

    IS - 2

    M1 - 19.2.5

    ER -