Skip to content

Research at St Andrews

Solving computational problems in the theory of word-representable graphs

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 if 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 if 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.
Close

Details

Original languageEnglish
Article number19.2.5
Number of pages17
JournalJournal of Integer Sequences
Volume22
Issue number2
Publication statusPublished - 24 Feb 2019

    Research areas

  • Word-representable graph, Representation number, Enumeration, Semi-transitive orientation, k-semi-transitive orientation

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. A framework for constraint based local search using ESSENCE

    Akgun, O., Attieh, S. W. A., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., Salamon, A. Z., Spracklen, P. & Wetter, J. P., 13 Jul 2018, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 1242-1248 7 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  2. Metamorphic testing of constraint solvers

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W., 2018, Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 727-736 (Lecture Notes in Computer Science; vol. 11008).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  3. Automatic discovery and exploitation of promising subproblems for tabulation

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W. & Salamon, A. Z., 2018, Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 11008).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  4. Automatically improving constraint models in Savile Row

    Nightingale, P., Akgün, Ö., Gent, I. P., Jefferson, C., Miguel, I. & Spracklen, P., Oct 2017, In : Artificial Intelligence. 251, p. 35-61 27 p.

    Research output: Contribution to journalArticle

  5. Exploiting short supports for improved encoding of arbitrary constraints into SAT

    Akgün, Ö., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W., 2016, Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. Rueher, M. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 9892).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related by journal

  1. S-crucial and bicrucial permutations with respect to squares

    Gent, I., Kitaev, S., Konovalov, A., Linton, S. & Nightingale, P., 3 Jun 2015, In : Journal of Integer Sequences. 18, 6, 22 p., 15.6.5.

    Research output: Contribution to journalArticle

  2. Equivalence classes of permutations under various relations generated by constrained transpositions

    Linton, S. A., Propp, J., Roby, T. & West, J., 2 Nov 2012, In : Journal of Integer Sequences. 15, 9, 23 p., 12.9.1.

    Research output: Contribution to journalArticle

  3. Sequences realized by oligomorphic permutation groups

    Cameron, P. J., 1 Dec 2000, In : Journal of Integer Sequences. 3, 1

    Research output: Contribution to journalArticle

ID: 258221847