On 1-11-representability and multi-1-11-representability of graphs

Tools

Alshammari, Mohammed and Kitaev, Sergey and Tang, Chaoliang and Tao, Tianyi and Zhang, Junchi (2025) On 1-11-representability and multi-1-11-representability of graphs. Utilitas Mathematica, 122. pp. 29-40. (https://doi.org/10.61091/um122-02)

[thumbnail of Alshammari-etal-UM-2025-On-1-11-representability-and-multi-1-11-representability-of-graphs]
Preview
 Text. Filename: Alshammari-etal-UM-2025-On-1-11-representability-and-multi-1-11-representability-of-graphs.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (483kB)| Preview

Abstract

Jeff Remmel introduced the concept of a k -11-representable graph in 2017. This concept was first explored by Cheon et al. in 2019, who considered it as a natural extension of word-representable graphs, which are exactly 0-11-representable graphs. A graph G  is k -11-representable if it can be represented by a word such that for any edge (resp., non-edge) xy  in G the subsequence of w formed by x  and y  contains at most k  (resp., at least k + 1 ) pairs of consecutive equal letters. A remarkable result of Cheon et al. is that any graph is 2-11-representable, while it is still unknown whether every graph is 1-11-representable. Cheon et al. showed that the class of 1-11-representable graphs is strictly larger than that of word-representable graphs, and they introduced a useful toolbox to study 1-11-representable graphs, which was extended by additional powerful tools suggested by Futorny et al. in 2024. In this paper, we prove that all graphs on at most 8 vertices are 1-11-representable hence extending the known fact that all graphs on at most 7 vertices are 1-11-representable. Also, we discuss applications of our main result in the study of multi-1-11-representation of graphs we introduce in this paper analogously to the notion of multi-word-representation of graphs suggested by Kenkireth and Malhotra in 2023.

ORCID iDs

Alshammari, Mohammed, Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647, Tang, Chaoliang, Tao, Tianyi and Zhang, Junchi;
  • Item type:Article
    ID code:92383
    Dates:
    Date
    Event
    22 March 2025
    Published
    7 March 2025
    Accepted
    29 January 2025
    Submitted
    Subjects:Science > Mathematics
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:19 Mar 2025 12:24
    Last modified:28 Mar 2025 14:54
    URI:https://strathprints.strath.ac.uk/id/eprint/92383
CORE (COnnecting REpositories)