Solving computational problems in the theory of word-representable graphs

MaRDI QIDQ3120420zbMATH OpenFDO

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

Publication date 4 March 2019

Full work available at URL https://arxiv.org/abs/1808.01215, https://cs.uwaterloo.ca/journals/JIS/VOL22/Kitaev/kitaev11.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

enumerationsemi-transitive orientationrepresentation numberword-representable graph\(k\)-semi-transitive orientation

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Combinatorics on words (68R15)

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 $xyinE$. 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. 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.

Recommendations

• Word-Representable Graphs: a Survey
• A comprehensive introduction to the theory of word-representable graphs
• New results on word-representable graphs
• On word-representable and multi-word-representable graphs
• Structural properties of word representable graphs
• scientific article; zbMATH DE number 219271
• The computational complexity of graph problems with succinct multigraph representation
• Word-representability of split graphs
• Word-representability of Toeplitz graphs
• Parikh word representable graphs and morphisms

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3318560 (Why is no real title available?)
• A comprehensive introduction to the theory of word-representable graphs
• Alternation graphs
• Automatically improving constraint models in Savile Row
• Colourability and word-representability of near-triangulations
• Graphs Capturing Alternations in Words
• Handbook of constraint programming.
• New results on word-representable graphs
• On 132-representable graphs
• On graphs representable by pattern-avoiding words
• On graphs with representation number 3
• On representable graphs
• On the Representability of Line Graphs
• On word-representability of polyomino triangulations
• Practical graph isomorphism. II.
• Semi-transitive orientations and word-representable graphs
• Word problem of the Perkins semigroup via directed acyclic graphs.
• Word-representability of face subdivisions of triangular grid graphs
• Word-representability of triangulations of grid-covered cylinder graphs
• Word-representability of triangulations of rectangular polyomino with a single domino tile
• Words and graphs
• \(S\)-crucial and bicrucial permutations with respect to squares

Cited in

(10)

• Human-verifiable proofs in the theory of word-representable graphs
• A comprehensive introduction to the theory of word-representable graphs
• An embedding technique in the study of word-representability of graphs
• New results on word-representable graphs
• On operations preserving semi-transitive orientability of graphs
• Word-Representable Graphs: a Survey
• Semi-transitive orientations and word-representable graphs
• Word-representable graphs: orientations, posets, and bounds
• Computing shortest 12-representants of labeled graphs
• On semi-transitive orientability of Kneser graphs and their complements

Describes a project that uses

Uses Software

• MINION
• Traces
• OEIS
• Yices
• nauty

This page was built for publication: Solving computational problems in the theory of word-representable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3120420)