Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 50 min ago
PreprintCC BY 4.0arXiv

On the representation number of chessboard graphs

  • Sergey Kitaev
  • Artem Pyatkin
Open at sourcePDFDOICite

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 to chessboard 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.

Related

  1. Crown graphs maximise the representation number of bipartite graphs
    Matthew J. Colbrook, Catherine Drysdale
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The v-number of powers of ideals associated with chessboard complexes
    Wenjie Huo, Guangjun Zhu, Jiaxin Li
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  3. A number field extension of Ramanujan's identity and its integral representation via the generalized Riemann Ξ-function
    Diksha Rani Bansal
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  4. On the k-Distance Chromatic Number of Unicyclic Graphs
    Rosário Fernandes, Rúben Palma
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeneral mathematicsDOAJ
  5. Representation Defects and Cassels Pairings for Congruent Number Curves: Rédei Symbols and Governing Fields
    Shisong Xu
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{kitaev2026representation,
  title = {{On the representation number of chessboard graphs}},
  author = {Sergey Kitaev and Artem Pyatkin},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.22311},
  eprint = {2609.22311},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.22311},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On the representation number of chessboard graphs
AU  - Sergey Kitaev
AU  - Artem Pyatkin
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.22311
UR  - https://arxiv.org/abs/2609.22311
AB  - 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 to chessboard 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.
ER  -