On the representation number of chessboard graphs | Sciact - Система учета научной деятельности ИМ СО РАН

On the representation number of chessboard graphs Научная публикация

Журнал

Acta Informatica
ISSN: 0001-5903 , E-ISSN: 1432-0525

Вых. Данные

Год: 2026, Том: 63, Номер статьи : 33, Страниц : 14 DOI: 10.1007/s00236-026-00547-w

Ключевые слова

Chessboard graph · Representation number · King graph · Queen graph · Rook graph · Bishop graph · Knight graph · Word-representable graph · Circle graph

Авторы

Kitaev Sergey ¹ , Pyatkin Artem ²

Организации

1	Department of Mathematics and Statistics, University of Strathclyde, 26 Richmond Street, Glasgow, G1, 1XH, United Kingdom
2	Sobolev Institute of Mathematics, Koptyug ave, 4, Novosibirsk, 630090, Russia

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0019

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.

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

Поступила в редакцию:	26 июл. 2025 г.
Принята к публикации:	14 сент. 2026 г.
Опубликована online:	18 сент. 2026 г.

≡ Web of science:	WOS:001878701300001
≡ Scopus:	2-s2.0-105051162266
≡ OpenAlex:	W7213554522