On the representation number of grid graphs and cylindric grid 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_ | 1866909699002073088 |
|---|---|
| author | Alshammari, Nawaf Shafi Kitaev, Sergey Pyatkin, Artem |
| author_facet | Alshammari, Nawaf Shafi Kitaev, Sergey Pyatkin, Artem |
| contents | The representation number of a graph is the minimum number of copies of each vertex required to represent the graph as a word, such that the letters corresponding to vertices $x$ and $y$ alternate if and only if $xy$ is an edge in the graph. It is known that path graphs, circle graphs, and ladder graphs have representation number 2, while prism graphs have representation number 3.
In this paper, we extend these results by showing that generalizations of the aforementioned graphs -- namely, the $m \times n$ grid graphs and $m \times n$ cylindrical grid graphs -- have representation number $3$ for $m \geq 3$ and $m \geq 2$, respectively, and $n\geq 3$. Furthermore, we discuss toroidal grid graphs in the context of word-representability, which leads to an interesting conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_16469 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the representation number of grid graphs and cylindric grid graphs Alshammari, Nawaf Shafi Kitaev, Sergey Pyatkin, Artem Combinatorics The representation number of a graph is the minimum number of copies of each vertex required to represent the graph as a word, such that the letters corresponding to vertices $x$ and $y$ alternate if and only if $xy$ is an edge in the graph. It is known that path graphs, circle graphs, and ladder graphs have representation number 2, while prism graphs have representation number 3. In this paper, we extend these results by showing that generalizations of the aforementioned graphs -- namely, the $m \times n$ grid graphs and $m \times n$ cylindrical grid graphs -- have representation number $3$ for $m \geq 3$ and $m \geq 2$, respectively, and $n\geq 3$. Furthermore, we discuss toroidal grid graphs in the context of word-representability, which leads to an interesting conjecture. |
| title | On the representation number of grid graphs and cylindric grid graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.16469 |