<abstract xmlns="http://www.w3.org/1999/xhtml"><p> Given a (symmetrically-moving) piece from a chesslike game, such as shogi, and an n×n board, we can form a graph with a vertex for each square and an edge between two vertices if the piece can move from one vertex to the other. We consider two pieces from shogi: the dragon king, which moves like a rook and king from chess, and the dragon horse, which moves like a bishop and rook from chess. We show that the independence number for the dragon kings graph equals the independence number for the queens graph. We show that the (independent) domination number of the dragon kings graph is n − 2 for 4 ≤ n ≤ 6 and n − 3 for n ≥ 7. For the dragon horses graph, we show that the independence number is 2n − 3 for n ≥ 5, the domination number is at most n−1 for n ≥ 4, and the independent domination number is at most n for n ≥ 5.</p></abstract>

Given a (symmetrically-moving) piece from a chesslike game, such as shogi, and an n×n board, we can form a graph with a vertex for each square and an edge between two vertices if the piece can move from one vertex to the other. We consider two pieces from shogi: the dragon king, which moves like a rook and king from chess, and the dragon horse, which moves like a bishop and rook from chess. We show that the independence number for the dragon kings graph equals the independence number for the queens graph. We show that the (independent) domination number of the dragon kings graph is n − 2 for 4 ≤ n ≤ 6 and n − 3 for n ≥ 7. For the dragon horses graph, we show that the independence number is 2n − 3 for n ≥ 5, the domination number is at most n−1 for n ≥ 4, and the independent domination number is at most n for n ≥ 5.

Independence and domination on shogiboard graphs

Recreational Mathematics Magazine

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Independence and domination on shogiboard graphs"}

Given a (symmetrically-moving) piece from a chesslike game, such as shogi, and an n×n board, we can form a graph with a vertex for each square and an edge...

Independence and domination on shogiboard graphs

Data publikacji: 11 sty 2018

Zakres stron: 25 - 37

DOI: https://doi.org/10.1515/rmm-2017-0018

Słowa kluczowe
shogi, n-queens problem, combinatorics

© 2018

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Independence and domination on shogiboard graphs

Data publikacji: 11 sty 2018

Zakres stron: 25 - 37

DOI: https://doi.org/10.1515/rmm-2017-0018

Słowa kluczoweshogi, n-queens problem, combinatorics

© 2018

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Słowa kluczowe
shogi, n-queens problem, combinatorics