On the representation number of chessboard graphs Full article
| Journal |
Acta Informatica
ISSN: 0001-5903 , E-ISSN: 1432-0525 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2026, Volume: 63, Article number : 33, Pages count : 14 DOI: 10.1007/s00236-026-00547-w | ||||
| Tags | Chessboard graph · Representation number · King graph · Queen graph · Rook graph · Bishop graph · Knight graph · Word-representable graph · Circle graph | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics, Siberian Branch of Russian Academy of Sciences, Novosibirsk, 630090, Russia | FWNF-2022-0019 |
Abstract:
The representation number of a graph is the smallest integer k such that the graph can be represented by a word in which each vertex appears exactly k times, and two distinct vertices x and y alternate in the word if and only if they are adjacent in the graph. We extend known results on the representation number for various graph classes tochessboard graphs—namely, king, queen, rook, bishop, and knight graphs. We provide a complete classification for queen graphs and partial classifications or observations for the other classes. As a consequence of our study, we obtain a characterization of all chessboard graphs that are circle graphs. Our work also leads to several interesting open problems.
Cite:
Kitaev S.
, Pyatkin A.
On the representation number of chessboard graphs
Acta Informatica. 2026. V.63. 33 :1-14. DOI: 10.1007/s00236-026-00547-w WOS Scopus OpenAlex
On the representation number of chessboard graphs
Acta Informatica. 2026. V.63. 33 :1-14. DOI: 10.1007/s00236-026-00547-w WOS Scopus OpenAlex
Dates:
| Submitted: | Jul 26, 2025 |
| Accepted: | Sep 14, 2026 |
| Published online: | Sep 18, 2026 |
Identifiers:
| ≡ Web of science: | WOS:001878701300001 |
| ≡ Scopus: | 2-s2.0-105051162266 |
| ≡ OpenAlex: | W7213554522 |