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.
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.
| Original language | English |
|---|---|
| Pages (from-to) | 29-40 |
| Number of pages | 12 |
| Journal | Utilitas Mathematica |
| Volume | 122 |
| DOIs | |
| Publication status | Published - 22 Mar 2025 |
Keywords
- 1-11-representable graph
- multi-1-11-representation of graphs
- word-representable graph
Fingerprint
Dive into the research topics of 'On 1-11-representability and multi-1-11-representability of graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver