On the representation number of grid graphs and cylindric grid graphs

Tools

Alshammari, Nawaf Shafi and Kitaev, Sergey and Pyatkin, Artem (2026) On the representation number of grid graphs and cylindric grid graphs. Journal of Automata, Languages and Combinatorics. ISSN 1430-189X (In Press)

[thumbnail of Alshammari-etal-JALC-2026-On-the-representation-number-of-grid-graphs-and-cylindric] Text. Filename: Alshammari-etal-JALC-2026-On-the-representation-number-of-grid-graphs-and-cylindric.pdf
Accepted Author Manuscript
Restricted to Repository staff only until 1 January 2099.
Download (858kB) | Request a copy

Abstract

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×n grid graphs and m×n cylindrical grid graphs -- have representation number 3 for m≥3 and m≥2, respectively, and n≥3. Furthermore, we discuss toroidal grid graphs in the context of word-representability, which leads to an interesting conjecture.

ORCID iDs

Alshammari, Nawaf Shafi, Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Pyatkin, Artem;
CORE (COnnecting REpositories)