On the Number of Edges for Chessboard Graphs in Higher Dimensions

Paul A. Burchett

Department of Mathematics, New River Community College, Dublin, VA, USA.

DOI: 10.4236/ojdm.2025.152003                

Abstract

In this paper, we consider chessboard graphs in higher dimensions and the number of edges of their corresponding graphs. First, we solve for the number of edges for some of the chessboard graphs of 3 dimensions. Then, we obtain results for the number of edges for higher dimensional chessboard graphs with all dimensions sizes being the same. For the higher dimensional queen’s graph, a double series solution for the number of edges was found - given both the dimension size and the number of dimensions. This solution didn’t reduce readily to a closed form solution. For the higher dimensional bishop’s graph, a series solution was found that involves the generalized Harmonic number. This solution series also didn’t readily reduce to a closed form solution. Results for the number of edges for two types of higher dimensional knights’ graphs were also found. Finally, a series solution for the number of edges for the higher dimensional king’s graph was found as well. To reduce this series solution to a closed form solution, the Wolfram Alpha series calculator was utilized.

Keywords

Chess, Queen’s Graph, King’s Graph, Bishop’s Graph, Knight’s Graph, Graph Theory, Edges

1. Introduction

There are many worthwhile questions that arise from considering chessboard graphs. Indeed, hundreds of papers have been written on the subject. This paper serves as a quick introduction to chessboard graphs in higher dimensions. As such, we will introduce chessboard movements in dimensions higher than 2. Since there can often be more than one way of extending a piece’s movement from 2-D into higher dimensions, we will mention only some of the possible extensions that the author has found in literature.

A very basic question regarding any graph is to ask for its number of edges. This question will serve as an introduction to chessboard graphs in higher dimensions. Note that there are many other questions that could be asked about chessboard graphs in higher dimensions. We will begin by looking at several papers that consider chessboard graphs in higher dimensions, as found in [1]-[3]. For two good surveys on other types of questions that might be fruitful, see [4] [5]. For questions on the general terminology used in this paper, see [6].

To construct a chessboard graph, we consider the movement of a particular piece on the standard 2-D board. The squares on the board are represented by vertices. Two vertices are said to be adjacent if and only if their corresponding squares are one movement of the given piece away from one another. We then say that two adjacent vertices have an edge between them. Note that each edge has two possible corresponding moves related to it. Thus, in non-specialist language, in this paper we’re finding the number of possible movements a particular piece can take on a given type of board and dividing this result by 2. This computes the number of edges for a given graph. We then say the degree of a vertex is the number of movements its corresponding square has away from that square. This is also the number of adjacent edges to the vertex.

The graphs we will consider in this paper for the lower dimension sizes are the 3-D rectangular bishop’s graph (denoted by B_m,n,r), the 3-D queen’s graph (denoted by Q_m,n,r), the 3-D king’s graph (denoted by K_m,n,r), the type one 3-D knight’s graph (denoted by N_n,m,r;1), and finally, the type two 3-D knight’s graph (denoted by N_n,m,r;2). Note that for these graphs m is the size of our first dimension, n is taken to be the size of our second dimension, and r is the size of our third dimension. We denote the number of edges for these graphs by |E(Q_m,n,r)|, |E(K_m,n,r)|, |E(N_n,m,r;1)|, and |E(N_n,m,r;2)|, respectively. All these values are found in this paper.

We will now begin to generalize these movements to higher dimensions. It is helpful to think of vertices as having coordinates for this endeavor. For the 2-dimensional rectangular boards, we have the coordinates (x, y) to denote a given vertex, with 1 ≤ x ≤ m, 1 ≤ y ≤ n, and x, y, m, and n all taken to be natural numbers. For the 3-D boards, we have the coordinates (x, y, z) to denote a given vertex, where 1 ≤ x ≤ m, 1 ≤ y ≤ n, and 1 ≤ z ≤ r (with all variables taken to be natural numbers). Note that, by symmetry, all graphs that have the same set of dimension sizes, regardless of what specific dimensions they’re the size of, are isomorphic. In other words, the corresponding graphs are structurally the same. We can then assume in these given proofs, without loss of generality, that our first variable has the lowest dimension size, that the second variable has a dimension size that is at least the dimension size of the first variable, but no greater than the third variable, and not consider the other graphs where such an ordering for the dimensions sizes doesn’t occur. This is because of the isomorphic nature of the graphs. Simply put, we can swap dimensions sizes any way we please and still have the same number of edges for the graph.

For a refresher, recall that the queen can move any number of squares either horizontally, vertically, or along a diagonal. It is then natural to consider the queen’s movements in higher dimensions to change any number of its coordinates by a constant absolute value. After all, a queen in 2-D changes either one of its square’s coordinates, or both of its square’s coordinates, by a constant absolute value that is allowable by dimension size. This is also the same movement for the d-dimensional queen as found in [3]. Note that for this queen’s movement, there will always be 3^d−1 directions for a queen to move when it is centrally located. This is because each coordinate can either increase or decrease by a constant amount (or stay the same) in a movement - but not all coordinates can stay the same in a movement. In this paper, we consider the queen’s graph in higher dimensions with all dimension sizes being of size n. We denote this graph by Q_n;d and denote the number of edges for this graph as |E(Q_n;d)|. In Theorem 18, we find a series solution for the number of edges in this graph. It should be noted that according to the Wolfram Alpha Series Calculator found, this series solution doesn’t readily reduce to a closed form solution.

A king can move up to one square away horizontally, vertically, or along a diagonal on a standard board. In higher dimensions, a king can move up to one space away in any direction allowable by dimension size. Thus, a king can change any number of its square’s coordinates either by subtracting or adding 1 to any number of coordinate values. In a similar fashion to the queen’s movement, a king can move in exactly 3^d−1 directions when the king is centrally located. In this paper, we consider the king’s graph in higher dimensions with the dimension sizes all taken to be of size n. We denote this graph by K_n;d and the number of edges for this graph by |E(K_n;d)|. The result for the number of edges in the 2-D king’s graph is found. In Theorem 19, we have a result on the number of edges for K_n;d in the cases for which d > 2. This result is obtained from finding a series solution and then using the Wolfram Alpha Series Calculator found in [7] to reduce the series solution to a closed form solution.

In 2 dimensions rooks can move any number of squares horizontally or vertically. A rook’s movement in two dimensions changes any one of its vertices’ two coordinates by any amount allowable by dimension size. We generalize this to higher dimensions by defining a rook’s move as changing exactly one of the coordinates by any amount allowable by dimension size. Although we don’t derive results for the higher dimensional rook’s graph above dimension size 3 (they’re trivial –as the rook’s graph is a regular graph), we do mention its movement in 3-D for the proof of Theorem 17.

A bishop can move any number of squares diagonally in 2 dimensions. By these rules, a bishop’s movement in two dimensions changes both of its square’s coordinates by a constant absolute value that is allowable by dimension size. It is then natural to define a bishop’s movements in higher dimensions as changing all its square’s coordinates by a constant absolute value that is allowable by dimension size. We denote the d-dimensional bishop’s graph by B_n,d and the number of edges for this graph by |E(B_n;d)|. In Theorem 20, we have a result for the number of given edges on B_n;d.

Finally, we come to the knight. The number of edges for the square, 2-D board is given in [5], and is 4(n − 1)(n − 2). A knight in 2-D changes both of its coordinates – one by an absolute value of one unit and the other by an absolute value of two units. Again, these movements are restricted by dimension size. One natural way to extend the knight’s movement to higher dimensions would then be to change exactly one coordinate by an absolute value of 1, a second, different coordinate by an absolute value of 2, a third, different coordinate by an absolute value of 3, etc., until we change all d coordinates in such a fashion. Extending the knight’s move in higher dimensions in such a way we call a type 1 knight’s movement. Our results for the knights’ graphs of higher dimensions greater than 3 are all when the dimension sizes are of size n. We denote the type 1 knight’s graph of d dimensions by N_n;d,1 and denote the number of edges for this graph by |E(N_n;d,1)|. In Theorem 21, we have a result for the number of edges on this graph.

The problem with a type 1 knight’s movement is that when the dimension size is either 0 (mod 4) or 3 (mod 4), the knight is restricted to squares of only one parity –either odd or even. Considering this, another type of movement for a knight in higher dimensions is given that solves this problem. For the type 2 knight’s movement one of the square’s coordinates is changed by an absolute value of 1, a second, different coordinate by an absolute value of 2, a third, different coordinate by an absolute value of 4, etc., up to a change of an absolute value of 2^d-1 in the last coordinate - where d is the number of dimensions. We denote this graph in higher dimensions as N_n;d,2 and the number of edges for this graph as |E(N_n;d,2)|. In Theorem 22, we arrive at a result for the number of edges for this graph.

For both types of knights’ graphs, we use some new terminology that needs to be introduced. We refer to a movement type with having exactly d coordinate values, with a ± symbol in front of each of the coordinate values. Each of the individual coordinate’s value changes by the absolute value change indicated. For example, the 4-D type 1 knight’s graph has the (±1, ±3, ±4, ±2) type indicating a set of movements that change the first coordinate by an absolute value of 1, the second coordinate by the absolute value of 3, the third coordinate by an absolute value of 4, and the fourth coordinate changing by an absolute value of 2. For this type of movement, there are exactly 16 classes of movements. Each movement class has the direction (positive or negative) specified. The reason we denote types is that due to symmetry, when we keep the dimension size the same for all our dimensions, all classes of movements under a given type have the same number of total corresponding movements (or edges) for the graph. We will see this new terminology in the proofs of Theorem 4 through Theorem 15.

2. Results

2.1. Three-Dimensional Results

Theorem 1 For $m\le n\le r$ , $\left|E\left(B_{m,n,r}\right)\right|=\frac{m\left(m-1\right)\left(m^2-2mn-2mr+m+6nr-2n-2r\right)}{3}$ .

Proof: For this proof we will be finding the sum of the degrees of all vertices of B_m,n,r and then divide by 2 to convert to the number of edges in the graph.

To begin to do this, we will first note that by symmetry the sum of the movements (among all vertices) in any one direction equals to the sum of the movements (among all vertices) in any other direction. For example, the direction where the x-coordinate and y-coordinate both increase and the z-coordinate decreases – denoted here by (+, +, −) - and the direction (+, −, −) have the same sum of movements. This is because if we consider the vertex (x, y, z) and the direction (+, +, −), then the number of edges in this direction for the vertex with associated coordinates (x, y, z) is the same as the number of edges in the direction (+, −, −) of the vertex (x, n + 1 − y, z) by symmetry. In a similar fashion, we find that the sum of the movements in any one direction equals to the sum of the movements in any of the 7 other directions.

We will begin by counting the sum of the degrees of the vertices by considering the direction (+, +, +), without loss of generality, and multiplying this result by 8. Note that there are (m − (m − 1))(n − (m − 1))(r − (m − 1)) − (m − m)(n − m)(r − m) vertices that have exactly m − 1 other squares along the direction (+, +, +). This is because we must have x = 1, y ≤ n − m + 1, and z ≤ r – m + 1 to have exactly m − 1 other squares along the direction (+, +, +). In a similar fashion, there are (m-(m − 2))(n − (m − 2))(r − (m − 2)) − (m − (m − 1))(n − (m − 1))(r − (m − 1)) squares with exactly m − 2 other squares along the direction (+, +, +). Continuing this pattern, we find that there are exactly (m − j)(n − j)(r − j) − (m − j − 1)(n − j − 1)(r − j − 1) squares with exactly j adjacent squares along the (+, +, +) direction. Summing these all up and multiplying by 8 for the number of directions gives us the expression $8{\displaystyle {\sum }_{j=1}^{j=m-1}j}\left(\left(m-j\right)\left(n-j\right)\left(r-j\right)-\left(m-j-1\right)\left(n-j-1\right)\left(r-j-1\right)\right)$ for the total number of moves. This equals the following sum:

$8{\displaystyle {\sum }_{j=1}^{j=m-1}\left(m-j\right)\left(n-j\right)\left(r-j\right)}$ . Multiplying through the three terms, then breaking the terms up by degrees of j, and finally using the rules for summation of cubes, squares, first degree variables, and constants (then dividing by 2) gives us $4\left(nrm\left(m-1\right)-\frac{m\left(m-1\right)}{2}\left(nr+nm+rm\right)+\left(n+r+m\right)\frac{m\left(m-1\right)\left(2m-1\right)}{6}-\frac{m^2{\left(m-1\right)}^2}{4}\right)$ . Factoring out common terms, distributing the 4, and combining like terms yields the proof. □

Theorem 2. For $4\le r$ , $\left|E\left(N_{2,3,r;1}\right)\right|=4\left(r-3\right)$ .

Proof: First, begin by noting there are exactly 8 different movement classes possible for this board. These are associated with the movement type (±1, ±2, ±3). All 8 of these movement classes have the same number of possible moves associated with them due to symmetry. Thus, we will consider the movement class (1, 2, 3), without loss of generality, and multiply the result by 8 for the total number of possible moves, then divide by 2 to convert from total possible moves to edges (or, multiply the result by 4).

Note that first to be able to have movement class (1, 2, 3) as a possible class of move for a square, a square must have coordinates of x = 1 and y = 1 since the maximum value for x is 2 and the maximum value of y is 3. This leaves us with only r − 3 possible moves since we must have z + 3 ≤ r and x and y values are set to one possible value. Then, since there are 8 possible directions, this gives us a total of 8(r − 3) for the total number of moves, or 4(r − 3) for the total number of edges for our graph. □

Theorem 3. For $4\le n\le r$ , $\left|E\left(N_{2,n,r;1}\right)\right|=8nr-20n-20r+48$ .

Proof: We will begin by noting there are exactly 16 possible movement classes for this board. These come from the movement types (±1, ±2, ±3) and (±1, ±3, ±2). Also note that all 8 movement classes in the type (±1, ±2, ±3) each have the same number of associated moves by symmetry. Likewise, all 8 movements classes in the type (±1, ±3, ±2) each have the same number of associated moves by symmetry.

We will first consider movement class (1, 2, 3), without loss of generality, and multiply the result by 8 to obtain all possible movements of the type (±1, ±2, ±3). It is easy to see that since x = 1, y + 2 ≤ n, and z + 3 ≤ r, then we have (n − 2)(r − 3) moves associated with the movement class (1, 2, 3) and 8(n − 2)(r − 3) total movements associated with the type (±1, ±2, ±3).

In a similar fashion, we next consider movements of the movement class (1, 3, 2), without loss of generality, and multiply this result by 8 to obtain all possible movements of the type (±1, ±3, ±2). Thus, since x = 1, y + 3 ≤ n, and z + 2 ≤ r, then we have (n − 3)(r − 2) moves associated with the movement class (1, 3, 2) and 8(n − 3)(r − 2) total moves associated with the type (±1, ±3, ±2).

Finally, we sum these two results to obtain 8(n − 3)(r − 2) + 8(n − 2)(r − 3) = 16nr − 40n − 40r + 96 for the total number of possible moves for this board. Dividing by two to go from the total number of possible moves to the number of edges gives us our result. □

Theorem 4. For $4\le r$ , $\left|E\left(N_{3,3,r;1}\right)\right|=16\left(r-3\right)$ .

Proof: We will begin by noting there are exactly 16 possible movement classes for this board. The types are (±1, ±2, ±3) and (±2, ±1, ±3). Note first that all 8 movement classes of the type (±1, ±2, ±3) and all 8 movement classes of the type (±2, ±1, ±3) have the same number of possible moves associated with them by symmetry. In fact, since we have the same dimension size for the first two dimensions, all 16 movement classes have the same number of possible moves associated with them by symmetry.

We will then consider movement class (1, 2, 3), without loss of generality, and multiply the result by 16 to obtain all possible movements. It is then easy to see that since 1 ≤ x ≤ 2, y = 1, and z + 3 ≤ r, then we have 2(r − 3) moves associated with the movement class (1, 2, 3), or 32(r − 3) total possible moves. Dividing by two to move from possible moves to the number of edges gives us our result. □

Theorem 5. For $4\le n\le r$ , $\left|E\left(N_{3,n,r;1}\right)\right|=4\left(3n-5\right)\left(r-3\right)+4\left(n-3\right)\left(3r-5\right)$ .

Proof: We will begin by noting there are exactly 32 possible movement classes for this board. These come from the movement types (±1, ±2, ±3), (±1, ±3, ±2), (±2, ±1, ±3), and (±2, ±3, ±1). Note that all 8 movement classes of any of the type (±1, ±2, ±3) each have the same number of associated moves by symmetry. Likewise, all 8 movement classes of the type (±1, ±3, ±2) have the same number of associated moves by symmetry. Finally, all 8 movement classes of the type (±2, ±1, ±3) have the same number of associated moves and all 8 movement classes of the type (±2, ±3, ±1) also have the same number of associated moves, by symmetry, for both types of 8 movement classes.

We will first consider movement class (1, 2, 3), without loss of generality, and multiply the result by 8 to obtain all possible movements of the type (±1, ±2, ±3). It is easy to see that since 1 ≤ x ≤ 2, y + 2 ≤ n, and z + 3 ≤ r, then we have 2(n − 2)(r − 3) movements in the movement class (1, 2, 3) and 16(n − 2)(r − 3) total moves associated with the movement type (±1, ±2, ±3).

In a similar fashion, we next consider movement class (1, 3, 2), without loss of generality, and multiply this result by 8 to obtain all possible movements of the type (±1, ±3, ±2). Thus, since 1 ≤ x ≤ 2, y + 3 ≤ n, and z + 2 ≤ r, then we have 2(n − 3)(r − 2) movements in the movement class (1, 3, 2) and 16(n − 3)(r − 2) total moves associated with the type (±1, ±3, ±2).

Next, we consider movements of the movement class (2, 1, 3), without loss of generality, and multiply this result by 8 to obtain all possible moves associated with type (±2, ±1, ±3). Thus, since x = 1, y + 1 ≤ n, and z + 3 ≤ r, then we have exactly 8(n − 1)(r − 3) possible moves for this type.

Finally, we consider movements of the movement class (2, 3, 1), without loss of generality, and multiply the result by 8 to obtain all possible movements for the type (±2, ±3, ±1). It is easy to see that since x = 1, y + 3 ≤ n, and z + 1 ≤ r, then we have (n − 3)(r − 1) movements in the type (2, 3, 1) and 8(n − 3)(r − 1) total moves associated with the type (±2, ±3, ±1). We then sum up all four results to obtain 16(n − 2)(r − 3) + 16(n − 3)(r − 2) + 8(n − 1)(r − 3) + 8(n − 3)(r − 1) = (r − 3)(16n − 32 + 8n − 8) + (n − 3)(16r − 32 + 8r − 8) = 8(r − 3)(3n − 5) + 8(n − 3)(3r − 5) for the total number of moves. Dividing this by 2 gives us the result. □

Theorem 6. For $4\le m\le n\le r$ , $\begin{array}{c}\left|E\left(N_{m,n,r;1}\right)\right|=4\left(m-1\right)\left(n-2\right)\left(r-3\right)+4\left(m-1\right)\left(n-3\right)\left(r-2\right)\\ +4\left(m-2\right)\left(n-1\right)\left(r-3\right)+4\left(m-2\right)\left(n-3\right)\left(r-1\right)\\ +4\left(m-3\right)\left(n-1\right)\left(r-2\right)+4\left(m-3\right)\left(n-2\right)\left(r-1\right)\end{array}$ .

Proof: Note there are 6 different movement types we will consider. Each of these types consists of 8 different movement classes which have the same number of edges in our graph. We will sum up all the movements over the 6 types for this proof.

For the first type we have the movement classes that correspond to (±1, ±2, ±3). Since any of these 8 classes of moves have the same number of edges in our graph, let us consider the movement class (1, 2, 3) without loss of generality. It is the case that there are exactly (m − 1)(n − 2)(r − 3) moves that correspond to this movement class. Thus, there are exactly 8(m − 1)(n − 2)(r − 3) moves for this movement class.

For the second type of movement classes that correspond to type (±1, ±3, ±2), it is straightforward to see there are exactly 8(m − 1)(n − 3)(r − 2) moves for this type. Likewise, it is easy to see that for the type of movement classes (±2, ±1, ±3) that there are exactly 8(m − 2)(n − 1)(r − 3) different movements.

It is then straightforward to see that for the remaining types of movement classes (±2, ±3, ±1), (±3, ±1, ±2), and (±3, ±2, ±1) there are exactly 8(m − 2)(n − 3)(r − 1), 8(m − 3)(n − 1)(r − 2), and 8(m − 3)(n − 2)(r − 1) moves associated with these types of movement classes, respectively. By summing all 6 of these results and dividing by 2 we obtain the proof. □

Theorem 7. For $5\le r$ , $\left|E\left(N_{2,3,r;2}\right)\right|=4\left(r-4\right)$ .

Proof: First, begin by noting there are exactly 8 different classes of moves possible for this board. These are associated with movement type (±1, ±2, ±4). All 8 of these classes have the same number of possible moves due to symmetry. Thus, we will consider the movement class (1, 2, 4), without loss of generality, and multiply the result by 8 for the total number of possible moves, then divide by 2 to convert from total possible moves to edges (or, in other words, multiply the result by 4).

Note that first to be able to have a (1, 2, 4) as a possible movement class for a square, a square must have coordinates for which x = 1 and y = 1 since the maximum value for x is 2 and the maximum value of y is 3. This leaves us with only r − 4 possible moves since we must have z + 4 ≤ r and x and y-values are set to one possible value. Then, since there are 8 possible directions, this gives us a total of 8(r − 4) for the total number of moves, or 4(r − 4) for the total number of edges for our graph. □

Theorem 8. For $5\le r$ , $\left|E\left(N_{2,4,r;2}\right)\right|=8\left(r-4\right)$ .

Proof: First, begin by noting there are exactly 8 different classes of movements possible for this board. These are associated with movement type (±1, ±2, ±4). All 8 of these movement classes have the same number of possible moves due to symmetry. Thus, we will consider the movement class (1, 2, 4), without loss of generality, and multiply the result by 8 for the total number of possible moves, then divide by 2 to convert from total possible moves to edges (or, in other words, multiply the result by 4).

Note that first to be able to have a (1, 2, 4) as a possible movement class for a square, a square must have coordinates for which x = 1 and y = 1 or y = 2 since the maximum value for x is 2 and the maximum value of y is 4. This leaves us with only 2(r − 4) possible moves since we must have z + 3 ≤ r, the x-values are set to one possible value, and the y-values are set to two possible values. Then, since there are 8 possible classes, this gives us a total of 16(r − 4) for the total number of moves, or 8(r − 4) for the total number of edges for our graph. □

Theorem 9. For $5\le n\le r$ , $\left|E\left(N_{2,n,r;2}\right)\right|=8\left(nr-3r-3n+8\right)$ .

Proof: First, begin by noting there are exactly 16 different classes of movements possible for this board. These are associated with the movement types (±1, ±2, ±4) and (±1, ±4, ±2). Note that all 8 classes associated with the type (±1, ±2, ±4) have the same number of possible moves, as do all 8 classes associated with the type (±1, ±4, ±2). Thus we will consider the movement class (1, 2, 4), without loss of generality, and multiply the result by 8 for the total number of possible moves associated with the type (±1, ±2, ±4). Then, we will consider the movement class (1, 4, 2), without loss of generality, and multiply the number of moves associated with it by 8. Finally, we will divide by 2 to convert from the number of possible moves to the total number of edges in our graph.

Note that first to be able to have a (1, 2, 4) as a possible movement class for a given square, this square must have coordinates for which x = 1 and y + 2 ≤ n and z + 4 ≤ r. This leaves us with only (n − 2)(r − 4) possible moves. Then, since there are 8 possible directions, this gives us a total of 8(n − 2)(r − 4) for the total number of moves associated with the movement type (±1, ±2, ±4).

Next, we will consider the movement class (1, 4, 2), without loss of generality. Note that first to be able to have a (1, 4, 2) as a possible movement class for a square, a square must have coordinates for which x = 1 and y + 4 ≤ n and z + 2 ≤ r. Thus, we have (n − 4)(r − 2) possible moves associated with movement class (1, 4, 2), or 8(n − 4)(r − 2) possible moves associated with the type (±1, ±4, ±2). Thus, there are 8(n − 2)(r − 4) + 8(n − 4)(r − 2) = 16(nr − 3r − 3n + 8) total moves. Dividing this by two we obtain 8(nr − 3r − 3n + 8) edges in our graph.□

Theorem 10. For $5\le r$ , $\left|E\left(N_{3,3,r;2}\right)\right|=16\left(r-4\right)$ .

Proof: First, begin by noting there are exactly 16 different classes of movements possible for this board. These are associated with movement types (±1, ±2, ±4) and (±2, ±1, ±4). Note that all 16 of these classes have the same number of possible moves since our first two dimensions are of the same size, namely 3. Thus, we will consider the movement class (1, 2, 4), without loss of generality, and multiply the result by 16 for the total number of possible moves. Finally, we will divide by 2 to convert from the number of possible moves to the total number of edges in our graph.

Note that first to be able to have a (1, 2, 4) as a possible movement class for a square, a square must have coordinates for which 1 ≤ x ≤ 2 and y = 1, and z + 4 ≤ r. This leaves us with only 2(r − 4) possible moves associated with the movement class (1, 2, 4). Multiplying this by 16 and dividing by 2 gives us a total of 16(r − 4) edges in our graph.□

Theorem 11. For $5\le r$ , $\left|E\left(N_{3,4,r;2}\right)\right|=28\left(r-4\right)$ .

Proof: First, begin by noting there are exactly 16 different movement classes possible for this board. These are associated with the types (±1, ±2, ±4) and (±2, ±1, ±4). Note both types consist of 8 movement classes that each have an equal number of possible moves associated with them. Thus, we will need only consider the movement classes (1, 2, 4) and (2, 1, 4), without loss of generality, then sum the results of these classes and multiply by 8 for the total number of possible moves on our board. Then, we divide by 2 to go from possible moves on our board to edges in our graph.

Consider then, without loss of generality, the movement class (1, 2, 4). It follows then that since we must have 1 ≤ x ≤ 2, 1 ≤ y ≤ 2, and z + 4 ≤ r, then there are exactly 4(r − 4) moves associated with this movement class. Next, consider the movement class (2, 1, 4). It follows that since x = 1, 1 ≤ y ≤ 3, and z + 4 ≤ r, then there are 3(r − 4) moves associated with this movement class. Summing these two results, multiplying the sum by 8, and dividing by 2 gives us the proof.□

Theorem 12. For $5\le n\le r$ , $\begin{array}{c}\left|E\left(N_{3,n,r;2}\right)\right|=8\left(n-2\right)\left(r-4\right)+8\left(n-4\right)\left(r-2\right)\\ +4\left(n-1\right)\left(r-4\right)+4\left(n-4\right)\left(r+1\right)\end{array}$ .

Proof: First, begin by noting there are exactly 32 different movement classes possible for this board. These are associated with the types (±1, ±2, ±4), (±1, ±4, ±2), (±2, ±1, ±4), and (±2, ±4, ±1). Note all these types consist of 8 movement classes that each have an equal number of possible moves associated with them. Thus, we will need only consider the movement classes (1, 2, 4), (1, 4, 2), (2, 1, 4), and (2, 4, 1), without loss of generality, then sum the results of these classes and multiply by 8 for the total number of possible moves on our board. Then, we divide by 2 to go from possible moves on our board to edges in our graph.

Consider then, without loss of generality, the movement class (1, 2, 4). It follows then that since we must have 1 ≤ x ≤ 2, y + 2 ≤ n, and z + 4 ≤ r then there are exactly 2(n − 2)(r − 4) moves associated with this movement class. Next, consider the movement class (1, 4, 2). It follows that since 1 ≤ x ≤ 2, y + 4 ≤ n, and z + 2 ≤ r, then there are 2(n − 4)(r − 2) moves associated with this movement class.

Next, consider the movement class (2, 1, 4). It is straightforward to see that there are (n − 1)(r − 4) moves associated with this movement class. Finally, consider movement class (2, 4, 1). It is easy to see that there are (n − 4)(r − 1) moves associated with this movement class. Summing these four results, multiplying the sum by 8, and dividing by 2 gives us the proof.□

Theorem 13. For $5\le r$ , $\left|E\left(N_{4,4,r;2}\right)\right|=48\left(r-4\right)$ .

Proof: First, begin by noting there are exactly 16 different movement classes possible for this board. These are associated with the types (±1, ±2, ±4) and (±2, ±1, ±4). Note both types consist of 8 movement classes that each have an equal number of possible moves associated with them. In fact, since the first two dimensions are of the same size, all 16 movement classes have an equal number of possible moves. Thus, we will need only consider the movement class (1, 2, 4), without loss of generality, and multiply by 16 for the total number of possible moves on our board. Then, we divide by 2 to go from possible moves on our board to edges in our graph.

Consider then, without loss of generality, the movement class (1, 2, 4). It follows then that since we must have 1 ≤ x ≤ 3, 1 ≤ y ≤ 2, and z + 4 ≤ r then there are exactly 6(r − 4) moves associated with this movement class. Multiplying this expression by 16 and then dividing by 2 gives us the proof.□

Theorem 14. For $5\le n\le r$ , $\begin{array}{c}\left|E\left(N_{4,n,r;2}\right)\right|=12\left(n-2\right)\left(r-4\right)+12\left(n-4\right)\left(r-2\right)\\ +8\left(n-1\right)\left(r-4\right)+8\left(n-4\right)\left(r-1\right)\end{array}$ .

Proof: First, begin by noting there are exactly 32 different movement classes possible for this board. These are associated with the types (±1, ±2, ±4), (±1, ±4, ±2), (±2, ±1, ±4), and (±2, ±4, ±1). Note all these types consist of 8 movement classes that each have an equal number of possible moves associated with them. Thus, we will need only consider the movement classes (1, 2, 4), (1, 4, 2), (2, 1, 4), and (2, 4, 1) without loss of generality, then sum the results of these classes and multiply by 8 for the total number of possible moves on our board. Then, we divide by 2 to go from possible moves on our board to edges in our graph.

Consider then, without loss of generality, the movement class (1, 2, 4). It follows then that since we must have 1 ≤ x ≤ 3, y + 2 ≤ n, and z + 4 ≤ r then there are exactly 3(n − 2)(r − 4) moves associated with this movement class. Next, consider the movement class (1, 4, 2). It follows that since 1 ≤ x ≤ 3, y + 4 ≤ n, and z + 2 ≤ r, then there are 3(n − 4)(r − 2) moves associated with this movement class.

Next, consider the movement class (2, 1, 4). It is straightforward to see that there are 2(n − 1)(r − 4) moves associated with this movement class. Finally, consider movement class (2, 4, 1). It is easy to see that there are 2(n − 4)(r − 1) moves associated with this movement class. Summing these four results, multiplying the sum by 8, and dividing by 2 gives us the proof.□

Theorem 15. For $5\le m\le n\le r$ , $\begin{array}{c}\left|E\left(N_{m,n,r;2}\right)\right|=4\left(m-1\right)\left(n-2\right)\left(r-4\right)+4\left(m-1\right)\left(n-4\right)\left(r-2\right)\\ +4\left(m-2\right)\left(n-1\right)\left(r-4\right)+4\left(m-2\right)\left(n-4\right)\left(r-1\right)\\ +4\left(m-4\right)\left(n-1\right)\left(r-2\right)+4\left(m-4\right)\left(n-2\right)\left(r-1\right)\end{array}$ .

Proof: Note there are 6 types of movements we will consider. Each of these types consists of 8 different movement classes which have the same number of edges in our graph associated with each of them. We will sum up all the movements over the 6 types for this proof.

The first type we have is (±1, ±2, ±4). Since any of these 8 movement classes have the same number of edges in our graph, let us consider the movement class (1, 2, 4), without loss of generality. It is the case that there are exactly (m − 1)(n − 2)(r − 4) moves that correspond to this movement class. Thus, there are exactly 8(m − 1)(n − 2)(r − 4) moves for these type of movements.

For the second type consider (±1, ±4, ±2). It is straightforward to see there are exactly 8(m − 1)(n − 4)(r − 2) moves for these type of movements. Likewise, it is easy to see that for the type of movements (±2, ±1, ±4) that there are exactly 8(m − 2)(n − 1)(r − 4) different movements.

It is then straightforward to see that for the remaining types (±2, ±4, ±1), (±4, ±1, ±2), and (±4, ±2, ±1) there are exactly 8(m − 2)(n − 4)(r − 1), 8(m − 4)(n − 1)(r − 2), and 8(m − 4)(n − 2)(r − 1) moves associated with these types, respectively. By summing all 6 of these results for the types and dividing by 2 we obtain the proof.□

Theorem 16 For $2\le m\le n\le r$ , $\begin{array}{c}\left|E\left(K_{m,n,r}\right)\right|=28+22\left(m+n+r-6\right)+17(\left(m-2\right)\left(n-2\right)+\left(m-2\right)\left(r-2\right)\\ +\left(r-2\right)\left(n-2\right))+13\left(m-2\right)\left(n-2\right)\left(r-2\right)\end{array}$ .

Proof: For this proof, we will be summing up the degrees of the vertices and dividing by 2. To start with, note there are 8 corner squares, each having corresponding vertices of degree 7. Dividing this by 2 gives us the constant value 28 in our sum.

Next, we consider the set of squares that all have exactly one coordinate which is either 1 or n. Note there are 4(m − 2) + 4(n − 2) + 4(r − 2) such squares. Each of these squares has a corresponding vertex of degree 11. It is easy to see that these 4(m + n + r − 6) vertices of degree 11 account for the 22(m + n + r − 6) term in the sum, if we keep in mind to divide by the 2.

Note there are 6 faces for our cube. Each of the faces has squares that would be interior squares for the face itself. These squares have exactly 2 coordinates that have values of either 1 or n. There are exactly 2(m − 2)(n − 2) + 2(m − 2)(r − 2) + 2(r − 2)(n − 2) such squares. Note all these squares have corresponding vertices of degree 17. Summing all these degrees up and dividing by 2 gives us the third set of terms in our sum.

Finally, note that there are (m − 2)(n − 2)(r − 2) squares that make up the interior of the cube. These squares are all of degree 26. It is then easy to see that dividing the sum of the degree of the vertices corresponding to the interior square by 2 gives us the final remaining term of our sum. □

Theorem 17. For $m\le n\le r$ , $\begin{array}{c}\left|E\left(Q_{m,n,r}\right)\right|=\left(\frac{m+n+r-3}{2}\right)mnr+rm\left(m-1\right)\left(n-\frac{m+1}{3}\right)\\ +nm\left(m-1\right)\left(r-\frac{m+1}{3}\right)+mn\left(n-1\right)\left(r-\frac{n+1}{3}\right)\\ +\frac{m\left(m-1\right)}{3}\left(m^2-2mn-2mr+m+6nr-2n-2r\right)\end{array}$ .

Proof: To begin note that the queen can move as a rook or a 3-D bishop – as well as moving to change exactly 2 of the coordinates. Since the 3-D rook’s graph is a regular graph with each vertex having degree m + n + r − 3, we have the first term in our sum. Also, by Theorem 1 we have the number of edges for the 3-D bishop’s graph. The last term in our sums contains this answer. It follows then that all we need to show is that the sum of the three middle terms in our sums equals the number of edges corresponding to movements that change exactly 2 of our coordinates.

Consider then movement that changes both the x-coordinate and the y-coordinate, but not the z-coordinate. It is clear then that the squares both before and after movement lie in a common plane. In fact, on any one of these planes we have edges corresponding to 2-D bishop’s movement on a rectangular board. Since the number of edges for the m×n bishop’s graph (for m ≤ n) is $m\left(m-1\right)\left(n-\frac{m+1}{3}\right)$ , and there is r such planes where we’re moving as a 2-D bishop (by changing both of the first two coordinates). That gives us the second expression in our sum.

The other two remaining terms in our sums (the third and fourth expressions to be summed) are found in a similar fashion. For example, we have n planes of movement equivalent to movement on B_m,r. This would mean to find the third expression of the sums we would use the same formula again with different variables (and noting that m ≤ r). For the fourth term, it is easy to see this term by using the same principles as in the second and third expressions to be summed. This gives us all five terms of our sum. □

2.2. D-Dimensional Results

Theorem 18. $\left|E\left(Q_{n;d}\right)\right|={\displaystyle {\sum }_{D=1}^{D=d}{2}^{D-1}\frac{d!}{D!\left(d-D\right)!}{n}^{d-D}{\displaystyle {\sum }_{j=1}^{n-1}{j}^D}}$ .

Proof: For this proof we will be summing up the degree of all the vertices then dividing the result by 2 to obtain the number of edges. To begin to do this, first consider all movements for which exactly D of our coordinates are changed (in other words, a D-dimensional move). Any one direction in which we change exactly D coordinates can be considered without loss of generality due to the symmetry obtained by having constant dimension size n for all our dimensions. First, note that there are $\frac{d!}{D!\left(d-D\right)!}$ ways to choose the D coordinates to change from our available d coordinates. Note also that there are 2D ways to assign direction given that we assign each of our D changing coordinates a positive or negative direction. It is straightforward to see that the coordinates that we’re not changing in our movement can take on any value from 1 to n. This means we multiply by a factor of n^d-D since there are going to be d − D coordinates that will not change value, and any of the n^d-D combination of values for these d-D coordinates can be considered, without loss of generality.

We will now begin summing up the number of edges by considering any direction in which exactly D of our coordinates are changed (say all our D coordinates are increasing by a common amount, without loss of generality). We will do this by considering sets of squares whose corresponding vertices all have the same number of adjacent edges in our corresponding direction. Note there is exactly one set of coordinate values for our D changing coordinates which offers up a set of squares with each square having exactly n − 1 adjacent squares (these initial squares have a value of 1 for all their D changing coordinates). Also, note there are exactly 2^D − 1 coordinates for our D changing coordinates which have n − 2 adjacent squares. Continuing this pattern, there are then j^D − (j − 1)^D coordinates for our D changing coordinates that offer up a set of squares with exactly n-j edges each. Summing up these edges gives us ${\displaystyle {\sum }_{j=1}^{j=n-1}\left(j^D-{\left(j-1\right)}^D\right)\left(n-j\right)}={\displaystyle {\sum }_{j=1}^{j=n-1}{j}^D}$ edges given that exactly D coordinates are changing. We then sum up the expression $j^D\frac{d!}{D\left(d-D\right)!}{n}^{d-D}{\displaystyle {\sum }_{j=1}^{j=n-1}{j}^D}$ over all our possible values for the number of changing coordinates – which is from 1 to d – to obtain the proof (and divide by 2 to move from the sum of degrees to the number of edges). □

Theorem 19. $\left|E\left(K_{n;d}\right)\right|={\displaystyle {\sum }_{D=1}^{D=d}{2}^{D-1}\frac{d!}{D!\left(d-D\right)!}{n}^{d-D}{\left(n-1\right)}^D}=\frac{n^d\left({\left(3-\frac{2}{n}\right)}^d-1\right)}{2}$ .

Proof: The proof for the series solution is very similar to the proof of Theorem 18, except that the inner summation equals ${\displaystyle {\sum }_{j=1}^{j=n-1}\left(j^D-j^{D-1}\right)}={\left(n-1\right)}^D$ . This follows since we have only 1 adjacent square per direction for the king’s graph, and not the n-j adjacent square(s) per direction as seen in the inner summation of Theorem 18. It is easy to see that with this one adjustment to Theorem 18 the proof of the series solution follows.

To see the closed form solution, the Wolfram Alpha series calculator was utilized. Wolfram Alpha is available online for free. See [8]. Below is the text entered into the input line of Wolfram Alpha:

Sum[2^(D-1)*n^(d-D)*d!/((d-D)!*D!)*(n − 1)^D] [{D] [1] [d}]. □

Theorem 20. $\left|E\left(B_{n;d}\right)\right|=2^{d-1}{\displaystyle {\sum }_{j=1}^{j=n-1}{j}^d}$ .

Proof: The proof follows by only summing the moves in the solution from Theorem 18 for which D = d and not summing from D = 1 to D = d. □

Theorem 21 $\left|E\left(N_{n;d,1}\right)\right|=2^{d-1}\frac{d!\left(n-1\right)!}{\left(n-d-1\right)!}$ for $n\ge d+1\ge 3$ .

Proof: In a similar fashion to Theorem 18, it follows that since the dimension sizes are the same then the sum of the edges for any one direction is the same as any other direction. Thus, consider the edges formed by the movement class (1, 2, 3, …, d). Note there are n − 1 first coordinates of our starting square that are acceptable for the move to be legal and n − 2 second coordinates for our starting square that allows the move, etc. This leaves us with $\left(n-1\right)!/\left(n-d-1\right)!$ possible coordinates, each having a legal move in our given direction.

Note this is the number of legal moves associated with one direction. Also note there are d! ways to assign the absolute value changes to the coordinates and 2^d ways to assign a positive or a negative sign to the absolute value changes in the coordinates. This gives us a total of 2^d × d! possible directions. Thus, we multiply our number of directions with the number of possible starting coordinates for a legal move and we obtain $2^{d}d!\left(n-1\right)!/\left(n-d-1\right)!$ possible moves. We then divide by two since we’re summing up the individual edges twice to obtain the result. □

Theorem 22. $\left|E\left(N_{n;d,2}\right)\right|=2^{d-1}d!{\displaystyle {\prod }_{j=0}^{j=d-1}\left(n-2^j\right)}$ for $n\ge 2^{d-1}+1\ge 3$ .

Proof: The proof of this theorem is like the proof of Theorem 21 in that there are 2^d × d! possible directions - and any direction will have the same number of edges associated with it by symmetry. Thus, we can consider the movement class (1, 2, 4, …, 2^d−1) solely, without loss of generality. Note that there are n − 1 possible choices for our first coordinate to allow for a legal move. Likewise, there are n − 2 possible choices for our second coordinate to allow for a legal move. Similarly, there are n − 2^j possible choices for the j + 1 coordinate to allow for a legal move. Multiplying these results together gives us ${\displaystyle {\prod }_{j=0}^{j=d-1}\left(n-2^j\right)}$ possible coordinates for a legal move, given the one direction. Thus, we have $2^{d}d!{\displaystyle {\prod }_{j=0}^{j=d-1}\left(n-2^j\right)}$ possible moves. Finally, we divide by two to obtain our result since the number of possible moves counts the number of edges twice. □

3. Discussion

In Theorem 20, a series solution was obtained for the number of edges in the higher dimensional bishop’s graph. The output given by Wolfram Alpha mentioned the generalized Harmonic series. One alternate form of the solution is $2^{d-1}\times H_{n-1}^{-d}$ , where $H_n^r$ is the generalized Harmonic number. Another alternate form for the solution was $2^{d-1}\left(\zeta \left(-d\right)-\zeta \left(-d,n\right)\right)$ , where $\zeta \left(s\right)$ is the Riemann Zeta function and $\zeta \left(s,a\right)$ is the Hurwitz Zeta function. Below is the input entered for Wolfram Alpha:

Sum[2^(d-1)*j^d] [{j] [1] [n − 1}].

The same series shows up as the inner series in the double summation for Theorem 20. When the double series solution for Theorem 20 was entered as input into the Wolfram Alpha series calculator, there was no output given. Below is the input given for the double series solution given in Theorem 20:

Sum[2^(D-1)*n^(d-D)*d!/((d-D)!*D!)*Sum[j^D] [{j] [1] [n − 1}], {D, 1, d}].

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Kumar, A. (2024) Magic Knight’s Tours in Higher Dimensions. arXiv: 1201.0458. https://arxiv.org/abs/1201.0458
[2]	Ripà, M. (2024) Proving the Existence of the Euclidean Knight’s Tours on n × n × ….. × n Chessboards for n < 4. arXiv: 2309.09639. https://arxiv.org/abs/2309.09639
[3]	Kunt, T. (2024). The n-Queens Problem in Higher Dimensions. arXiv: 2406.06260. https://arxiv.org/abs/2406.06260
[4]	Hedetniemi, J. and Hedetniemi, S.T. (2021) Structures of Domination in Graphs: Domination in Chessboard. Springer.
[5]	Watkins, J.J. (2004) Across the Board: The Mathematics of Chessboard Problems. Princeton University Press. https://doi.org/10.1515/9781400840922
[6]	Chartrand, G. and Lesniak, L. (1996) Graphs & Digraphs. Chapman & Hall/CRC.
[7]	(2024) Wolfram α Series Calculator. https://www.wolframalpha.com/input?i=sum+of+a+series