On 1-11-representability and multi-1-11-representability of graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909464624365568 |
|---|---|
| author | Alshammari, Mohammed Kitaev, Sergey Tang, Chaoliang Tao, Tianyi Zhang, Junchi |
| author_facet | Alshammari, Mohammed Kitaev, Sergey Tang, Chaoliang Tao, Tianyi Zhang, Junchi |
| contents | 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 $w$ 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 at 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_13871 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On 1-11-representability and multi-1-11-representability of graphs Alshammari, Mohammed Kitaev, Sergey Tang, Chaoliang Tao, Tianyi Zhang, Junchi Combinatorics 05C62 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 $w$ 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 at 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. |
| title | On 1-11-representability and multi-1-11-representability of graphs |
| topic | Combinatorics 05C62 |
| url | https://arxiv.org/abs/2501.13871 |