Solving computational problems in the theory of word-representable graphs

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

Research output: Contribution to journalArticle

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.
LanguageEnglish
Article number19.2.5
Pages1-18
Number of pages18
JournalJournal of Integer Sequences
Volume22
Issue number2
Publication statusPublished - 24 Feb 2019

Fingerprint

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

Keywords

  • word-representable graph
  • semi-transitive orientation
  • representation number
  • enumeration
  • k-semi-transitive orientation

Cite this

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, No. 2. pp. 1-18.
@article{3c4f8e3aec0a4cf685fe55e34b1a04d5,
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 = "word-representable graph, semi-transitive orientation, representation number, enumeration, k-semi-transitive orientation",
author = "{\"O}zg{\"u}r Akg{\"u}n and Ian Gent and Sergey Kitaev and Hans Zantema",
year = "2019",
month = "2",
day = "24",
language = "English",
volume = "22",
pages = "1--18",
journal = "Journal of Integer Sequences",
issn = "1530-7638",
number = "2",

}

Akgün , Ö, Gent, I, Kitaev, S & Zantema, H 2019, 'Solving computational problems in the theory of word-representable graphs' Journal of Integer Sequences, vol. 22, no. 2, 19.2.5, pp. 1-18.

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, No. 2, 19.2.5, 24.02.2019, p. 1-18.

Research output: Contribution to journalArticle

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/2/24

Y1 - 2019/2/24

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 - word-representable graph

KW - semi-transitive orientation

KW - representation number

KW - enumeration

KW - k-semi-transitive orientation

UR - https://cs.uwaterloo.ca/journals/JIS/VOL22/Kitaev/kitaev11.html

M3 - Article

VL - 22

SP - 1

EP - 18

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 -