Journal of Integer Sequences, Vol. 27 (2024), Article 24.3.7

Domination Polynomial of the Rook Graph


Stephan Mertens
Institut für Physik
Otto-von-Guericke Universität Magdeburg
Postfach 4120
39016 Magdeburg
Germany
and
Santa Fe Institute
1399 Hyde Park Rd
Santa Fe, NM 87501
USA

Abstract:

A placement of chess pieces on a chessboard is called dominating if each free square of the chessboard is under attack by at least one piece. In this contribution we compute the number of dominating arrangements of k rooks on an n × m chessboard. To this end we derive an expression for the corresponding generating function, the domination polynomial of the n × m rook graph.


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequences A006075 A055599 A075458 A287274 A368831.)


Received December 31 2023; revised version received March 5 2024. Published in Journal of Integer Sequences, March 9 2024.


Return to Journal of Integer Sequences home page