### Uittreksel

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.

Taal | Engels |
---|---|

Artikelnummer | 19.2.5 |

Aantal pagina's | 18 |

Tijdschrift | Journal of Integer Sequences |

Volume | 22 |

Nummer van het tijdschrift | 2 |

Status | Gepubliceerd - 2019 |

### Vingerafdruk

### Trefwoorden

### Citeer dit

*Journal of Integer Sequences*,

*22*(2), [19.2.5].

}

*Journal of Integer Sequences*, vol. 22, nr. 2, 19.2.5.

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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer 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 -