Received 8 April 2016; accepted 11 July 2016; published 14 July 2016

ABSTRACT

Both independence and independence-separation problems on chessboard graphs have been studied in detail, with hundreds of papers in the broader independence category, and several on the independence-separation problem variant for chessboard graphs. In this paper, the inde- pendence-separation problem is considered on the d-dimensional rook’s graph. A lower bound of k, for, is found for the independence-separation number on the d-dimensional rook’s graph, denoted by. For the case where, it is found that when n is odd and,. Conjecture and discussion are added.

Keywords:

Chess, Independence-Separation Number, Independence Number, p-Dimensional Grid-Line Graphs, p-Dimensional Rook’s Graph

1. Introduction

The topic of independence on chessboard graphs was first considered in 1848 by chess composer and enthusiast Max Bezzel, when Bezzel considered the queen’s independence problem on the standard board. In this paper, we consider a variant of this type of question whose two-dimensional equivalent has been studied in detail [1] - [5] . In this separation-problem variant, first considered with queens and separating pawns on boards in [5] , we’re allowed to block the attack of any of our pieces, rooks being the type, in our 3-D board by placing pawns between any two otherwise adjacent rooks, with a rook’s movement in 3-D being any number of unit cubes in one of the up, down, left, right, in, or out directions. Normally, with no such pawns allowed, the independence number on the 3-D rook’s graph is. With pawns allowed our problem becomes, what is the minimum number of blocking pawns needed so that we can place at most independent rooks in a cube, with only considered here? The answer to this question, denoted, is

shown to have a lower bound of k, for, which is obtained when n is odd and

.

One can also further extend these types of questions to include graphs with arbitrary dimension. Note that normally, with no blocking pawns, the cardinality of any maximal set of non-attacking rooks, or the inde- pendence number on the d-dimensional rook’s graph, is. The independence-separation number of the d-dimensional rook’s graph, or of the equivalent p-dimensional grid-line graph, is denoted by for, and is the minimum number of blocking pawns needed to separate rooks in our d-

dimensional rook’s graph. In this paper it is shown that for,. Note that values for do not exist for since at most rooks can be

separated by pawns on the d-dimensional rook’s graph.

2. Results

Theorem 1. For all, with,.

Proof: We begin by considering 1-D slices that all have the same coordinates, save for one of their d coordinates, without loss of generality, say the first coordinate. Any one of these slices is equivalent to the subgraph induced by the n vertices whose n corresponding entries differ only in their first coordinates. Note each such slice, and there are of them, have vertex sets that are disjoint, and each vertex in any one of the sets can be paired in a 1-1 fashion with each combination of coordinates from the second coordinate through coordinate number d.

Let with be the number of such 1-D slices that are occupied by at least one rook. Then it is known that since the total number of rooks minus the total number of 1-D slices with rooks would leave exactly excess rooks, with the need for at least as many blocking pawns.

Theorem 2. For n is odd and,.

Proof: Note that by Theorem 1, when. We will now show that for.

Begin by considering the entries of the alternating sign matrix as seen in [6] . Associate with the one entries in our matrix a rook placement, zero entries as an empty square, and negative one entries a pawn placement using the same row and column as the corresponding matrix entry. To start our placement, place rooks and pawns by converting the entries of the alternating sign matrix into the center-most two-dimensional slice of our cube among those 2-D slices that have no height. Then, place pawns and rooks in each of the two directly adjacent two-dimensional slices, whose induced subgraph is equivalent to the rook’s graph, by placing pawns directly adjacent, both downward and upward, to the already placed rooks. The exception is that, taking the origin to be the center of the center square, pawns are not placed on the diagonals having sums or differences

of plus or minus. Also, place rooks in these same two, two-dimensional slices by placing them directly

adjacent to the pawns in our considered, center-most 2-D slice. Next, place 4 rooks in these same two, 2-D slices by placing them two at a time, beginning with the 2-D slices directly upwards from the center. There, place a pair of rooks in one pair of opposite corners of this, 2-D slice of vertices. Then, for the other 2-D slice that has a depth and length of n vertices, and null height, place two rooks in the only available opposite, corner squares of our 2-D slice.

This finishes the first part of our step process. To see the second step and beyond to step b, we will

begin by placing rooks and pawns similar to step one, by placing rooks and pawns directly adjacent to pre- viously placed rooks and pawns in our inductive process, save for placing rooks in corner squares, or the pawns that would be placed along diagonals having coordinates that have a sum or difference of plus or minus

. Instead, place rooks in the sum diagonals with sums of or in the bottom-most 2-D

slice in the pair of 2-D slices first considered at step b. In the top-most of the pair, place rooks as a reflection of the bottom-most 2-D slice under consideration by reflecting the formation of rooks and pawns about either of its axes of symmetry.

Note since, then and. This implies that none of

the rooks placed in the alternating and occupied, center squares are vertically adjacent to the rooks placed along diagonals with the sum of or; since the 2-D projection of the diamond formation seen in [6] onto any of the non-center 2-D slices must be between diagonals having sum or differences of coordinates inclusively

between minus and plus.

Also, because the top-most 2-D slice of the pair considered first in step b is a reflection, and also the 2-D projection of the diamond formation onto any of the slices is symmetric about either of the axes of symmetry as well, then the rooks placed in the top-most 2-D slice between the pair of 2-D slices considered at step b can’t be adjacent to our center-most, occupied squares―since this would imply the adjacency of the recently placed, bottom―most rooks outside of our occupied, center squares would be adjacent to the occupied center. Finally, no rooks are adjacent either row or column-wise by design.

Figures 1-7 will illustrate a formation. Figure 1 will represent our bottom 2-D slice, while the

top slice will be the bottom slice reflected across one of its axes of symmetry. In a similar way, Figure 2 will represent the 2-D slice that is one unit from the bottom 2-D slice, while the reflection of Figure 2 across either of its axes of symmetry represents the 2-D slice that is a unit down from the top. We continue pairing the figures, and their reflections, with two, 2-D slices; moving in the bottom-half up, and in the top-half down. The only exception is that Figure 7 represents the center slice.

To count our pawns, first note that the bottom and top slice have no pawns placed in them. Then, note that the jth, and the 2-D slice, moving from bottom to top, both have pawns in them. Summing

from to of, multiplying this by two for each slice with pawns placed in

them, and finally adding in the center 2-D slice’s pawns, we obtain pawns in

our count.

Before counting our number of rooks note that the count on the total number of rooks subtract, is equal to the k-value. Thus, it follows that if the k-value matches the number of pawns in the above count, the theorem is proven.

To begin counting first note that the jth 2-D slice, counting from bottom to top, and the 2-D slice

have the same number of rooks in them. Also, note that in the jth slice, with, we have rooks, and in the center slice we have rooks. Thus multiplying 2 by the sum from to of, then adding in our gives us for our total number of rooks. Then, subtracting out, we obtain, which is both the value for k and our total number of

pawns, thereby ending the proof.

Conjecture 1. For n is odd with, if and only if

.

Similar patterns as those used in [6] , for the center slices and even n, and a similar process as shown in this paper might lead to similar types of theorems for even n and. Note that and when, thereby not contradicting the conjecture when.

Acknowledgements

The author would like to thank Dr Doug Chatham for friendly advice.

Cite this paper

Paul A. Burchett, (2016) The Independence-Separation Problem on the 3-D Rook’s Graph. Open Journal of Discrete Mathematics,06,167-173. doi: 10.4236/ojdm.2016.63014

References