Problem of the Month
(October 2013)

A digraph, or directed graph, is a collection of points and arrows between points, with no more than 1 arrow from a point to any other point, and no arrow from a point to itself. An n-regular digraph is a digraph that has n arrows coming out of and going into every point. How many 1-regular and 2-regular digraphs are there with n points?

Given such a digraph, can it be realized by a chess position in which the points represent chess pieces (no pawns), and there is an arrow from A to B only if piece A attacks piece B? If so, what is the smallest chessboard (in terms of area) on which this can occur?

The same questions can be asked for 3-regular digraphs, though they may be hard to count, and even harder to realize with chess positions. Can you show that no 4-regular digraph is realizable with a chess position?

ANSWERS

The smallest-known chessboards are shown below.

Chess Positions Representing 1-Regular Digraphs
2 3 4 5

(Richard Sabey)

6 7

(Andrew Bayly)
(Andrew Bayly)
(Joe DeVincentis)
(Andrew Bayly)
(Andrew Bayly)

8

(Andrew Bayly)
(Andrew Bayly)
(Andrew Bayly)
(Maurizio Morandi)
(Andrew Bayly)
(Andrew Bayly)
(Andrew Bayly)

9

(Andrew Bayly)
(Andrew Bayly)
(George Sicherman)
(George Sicherman)
(Andrew Bayly)
(Andrew Bayly)
(Andrew Bayly)
(Andrew Bayly)

Joe DeVincentis showed that the number of 1-regular digraphs is A002865 at the OEIS.

Joe Devincentis showed that every 1-regular digraph can be realized as a chess position.

Chess Positions Representing 2-Regular Digraphs
3 4 5

(Maurizio Morandi) 		none

6

(Maurizio Morandi)
(Andrew Bayly)
(Andrew Bayly) 		none
(Joe DeVincentis)
(Maurizio Morandi)

6

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

6

(Maurizio Morandi) 		? ? ?
(Mark Thompson) 		none
(Mark Thompson)
(Joe DeVincentis)
(Mark Thompson)

Chess Positions Representing 3-Regular Digraphs
Apparently most (if not all) 3-regular graphs can be represented with only queens (see the August 2005 Math Magic). Are there smaller solutions for other piece sets?


(Dave Langers)
(Dave Langers)
(Dave Langers)
(Dave Langers)
(Dave Langers)
(Dave Langers)

Here are some 3-regular graphs realized by only knights, one of which comes from February 2007 Math Magic:


(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)

Most 3-regular digraphs with one or more directed edges can not be realized with chess positions. Here are a few that can be, using only queens and knights. Can you find any others?


(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

Here are some others that use different pieces too:


(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Andrew Bayly)
(Maurizio Morandi)

Chess Positions Representing 4-Regular Digraphs
Joe DeVincentis pointed out there ARE 4-regular graphs that are realizable with chess positions, some of which appeared in the August 2005 Math Magic. Can you find any others?

(Geoff Exoo)
(Geoff Exoo)
(Joe DeVincentis)
(Maurizio Morandi)


(Joe DeVincentis)

Here are some with directed edges, using queens and knights:


(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
Here are some others that use different pieces too:


(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Maurizio Morandi)
(Maurizio Morandi)

(Maurizio Morandi)
(Andrew Bayly)

Joe DeVincentis showed there are no 5-regular graphs or digraphs realizable with the usual chess pieces. What fairy chess pieces used in the August 2005 Math Magic have 5-regular realizations? George Sicherman found the positions below using amazons and archbishops:


(George Sicherman)
(George Sicherman)

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 12/28/13.