The Number of Minimum Roman and Minimum Total Dominating Sets for Some Chessboard Graphs

Paul A. Burchett

Independent Researcher, Pulaski, VA, USA.

DOI: 10.4236/ojdm.2020.101004                

Abstract

In this paper, both the roman domination number and the number of minimum roman dominating sets are found for any rectangular rook’s graph. In a similar fashion, the roman domination number and the number of minimum roman dominating sets are found on the square bishop’s graph for odd board sizes. Also found are the number of minimum total dominating sets associated with the light-colored squares when n ≡ 1(mod12)  (with n>1), and same for the dark-colored squares when n ≡ 7(mod12) .

Keywords

Total Domination, Roman Domination, Bishop’s Graph, Rook’s Graph, Chess

1. Introduction

The $m\times n$ rook’s graph, denoted by $R_{m\mathrm{,}n}$, is formed by associating the squares of our $m\times n$ board with vertices. Two vertices are adjacent on the rectangular rook’s graph if and only if their corresponding squares share a common row or column. Similarly, the square bishop’s graph is denoted by $B_n$, and is formed by associating the squares of our $n\times n$ board with vertices. Two vertices are adjacent on the Bishop’s graph if and only if their corresponding squares lie on a common diagonal. Many areas of interest have been studied for the chessboard graphs, including domination parameters. For a good summary of the sub-field, see [1].

Given a graph $G=\left(V,E\right)$ and a function $f\mathrm{<mo>\; :\; </mo>}V\to \left\{\mathrm{0,1,2}\right\}$, then a set of vertices is a roman dominating set if and only if for every vertex $v\in V$ such that $f\left(v\right)=0$ has a neighbor $u\in V$ with $f\left(u\right)=2$. The weight of the roman dominating function is $w\left(t\right)={\displaystyle {\sum }_{v\in V}}f\left(v\right)$. The roman domination number of a graph G, denoted by ${\gamma }_r\left(G\right)$, is the minimum weight of all possible roman dominating functions. In this paper, the roman domination number for our $m\times n$ rook’s graph is denoted by ${\gamma }_r\left(R_{m\mathrm{,}n}\right)$, or ${\gamma }_r\left(R_n\right)$ for the square, $n\times n$ rook’s graph. In a similar way, ${\gamma }_r\left(B_n\right)$ denotes the roman domination number on the square, $n\times n$ bishop’s graph. For more on the roman domination parameter in general, including some work for specific families of graphs, see [2] - [9].

Likewise, given a graph $G=\left(V,E\right)$, a set of vertices is said to be a total dominating set if every vertex in V is adjacent to at least one vertex in the set. The minimum cardinality among all total dominating sets is known as the total domination number, denoted ${\gamma }_t\left(B_n\right)$ for the bishop’s graph. On the bishop’s graph, a set can also be said to be a total dominating set if and only if every square is attacked. The total domination number for the bishop’s graph was

determined to be $2\lceil \frac{2\left(n-1\right)}{3}\rceil$ for $n\ge 3$ in 1986 [10]. This paper’s findings also imply that for $n\equiv 1\left(\mathrm{mod}12\right)$ (with $n>1$ ), the total domination number of the subgraph associated with the light-colored squares is $\frac{2\left(n-1\right)}{3}$, and the

same when $n\equiv 7\left(\mathrm{mod}12\right)$ for the subgraph associated with the dark-colored squares. These findings are central to the results in Section 4 of this paper. For more on the total domination number, a good book on the current literature is [11].

2. Rook’s Graph Results for Roman Domination

Theorem 1. ${\gamma }_r\left(R_n\right)=2n-1$.

Proof: Consider any $n\times n$ board. Denote a to be the number of two entries placed on vertices associated with the squares of our board. Denote b to be the number of vertices that have ones placed in them. Note that we have, at least, $n-a$ rows and $n-a$ columns that have no two entries placed in them. Thus, the number of squares which would have one entries planted in them is, at least, ${\left(n-a\right)}^2$. It follows that since ${\gamma }_r\left(R_n\right)=2a+b$, then $2a+{\left(n-a\right)}^2\le 2a+b={\gamma }_r\left(R_n\right)$, which is our answer. Simplifying, and noting that $2a+{\left(n-a\right)}^2$ is a quadratic where a is our variable, we simplify to $a^2+2a\left(1-n\right)+n^2$. But since this quadratic has a minimum at $a=n-1$, then ${\gamma }_r\left(R_n\right)=2a+b\ge 2a+{\left(n-a\right)}^2\ge {\left(n-1\right)}^2+2\left(n-1\right)\left(1-n\right)+n^2=2n-1$. To see that ${\gamma }_r\left(R_n\right)\le 2n-1$, then place twos in every square along one of the main diagonals—save for one of those squares. In this square, plant a one. This provides a roman dominating set of size $2n-1$. Figure 1 will illustrate. $\square$

Theorem 2. For $n>m$, ${\gamma }_r\left(R_{m\mathrm{,}n}\right)=2m$.

Proof: To begin our proof we will first define a subgraph G of the $m\times n$ rook’s graph similar to the ones first introduced in [12] [13] for the queen’s graph, with the vertex set taken to correspond to the two entries. Our subgraph G differs from the definition given for the queen’s graph in that there are no diagonal edges for G on the rook’s graph, just column and row edges. Given the

Figure 1. Let the pawn in the lower-left hand corner represent a one entry and the rooks represent two entries. Then the above is a minimum roman dominating set for the standard 8×8 board.

subgraph of vertices associated with our two entries as our vertex set, two vertices are adjacent in G if and only if when we place rooks on all the squares associated with the two entries, these squares attack one another via unoccupied squares. For example, if there are exactly 5 two entries in a single column, there will be exactly 4 column edges associated with this column.

Let r be the number of such row edges in G, and c the number of column edges. Also assume that $n>m$ and the number of two entries is $m-j$ for some natural number j with $0<j\le m$ (note if $j\le 0$ then by necessity ${\gamma }_r\left(R_{m\mathrm{,}n}\right)\ge 2m$ ). It then follows that the number of empty columns will be $n-m+j+c$ and the number of empty rows is $j+r$. Thus our Roman domination number is, at least, ${\gamma }_r\left(R_{m,n}\right)=2\left(m-j\right)+\left(n-m+j+c\right)\left(j+r\right)\ge 2\left(m-j\right)+2j$, or ${\gamma }_r\left(R_{m\mathrm{,}n}\right)\ge 2m$, since the number of one entries will be the number of squares where the unoccupied rows and columns intersect.

To see that indeed ${\gamma }_r\left(R_{m\mathrm{,}n}\right)\le 2m$, place m two entries, each having a different row. It is then easy to see that any square will be in the same row with at least one two entry, and thereby be roman dominated. Figure 2 will illustrate. $\square$

Theorem 3. The number of minimum Roman Dominating sets for the square rook’s graph is $n\left(n\mathrm{<mo>\; !\; </mo>}\right)$, where n is the length of both of our dimensions.

Proof: First note it follows that we must have exactly $n-1$ two entries, and the lone, one entry placed on our $n\times n$ board, since our quadratic in Theorem one had its only minimum at $a=n-1$, leaving us with the sole, one entry to provide our count of $2n-1$ for the roman dominating set. It also follows that each entry can’t share the same row or column, for if either any single pair of two entries share a row (or column, without loss of generality) then we’d have ${\gamma }_r\left(R_n\right)\ge 2\left(n-1\right)+2=2n$, a contradiction. Also note no two entry can be adjacent to our lone one entry, for if so we can then obtain a roman dominating set with less cardinality than our proven minimum by changing the associated one entry to a zero entry, thereby a contradiction.

Making no distinction between the $n-1$ two entries and the sole one entry, we note we can associate these n objects with independent vertices on our board

Figure 2. Let the rooks be associated with two entries. Then the above is one minimum roman dominating set for an 8 × 9 board.

$n\mathrm{<mo>\; !\; </mo>}$ ways. Then, noting that there are, for any such placement, n ways to choose one of our n objects to be associated with the only one entry, and the other $n-1$ objects associated with the two entries. Multiplying the results gives us $n\left(n\mathrm{<mo>\; !\; </mo>}\right)$ for the number of minimal roman dominating sets. $\square$

Theorem 4. The number of minimum Roman Dominating sets for the $m\times n$ rook’s graph, with $n=m+1$, is ${\left(m+1\right)}^m+\left(m\mathrm{<mo>\; !\; </mo>}\right)\left(\frac{m\left(m+1\right)}{2}\right)$.

Proof: First we will show that there are two classes of solutions when $n=m+1$. The first class of solutions simply places the two entries, one per row, until we have our count of m two entries. It is easy to see that since there are $m+1$ possibilities for any row, and there are m rows, then there are ${\left(m+1\right)}^m$ sets in this class. Figure 2 illustrates an example of a minimum roman dominating set, where $n=m+1$, in this class of solutions.

Next consider again, as in Theorem 2, the inequality

${\gamma }_r\left(R_{m,n}\right)=2\left(m-j\right)+\left(n-m+j+c\right)\left(j+r\right)2\left(m-j\right)+2j$

where $j\ge 1$. Now assume $j\ge 2$. Thus ${\gamma }_r\left(R_{m,n}\right)=2\left(m-j\right)+\left(1+j+c\right)\left(j+r\right)\ge 2m-2j+\left(1+j\right)\left(j\right)$, or ${\gamma }_r\left(R_{m,n}\right)=2m-j+j^2>2m$, which is a contradiction. Thus for our second class of solutions it follows that we must have $j=1$, $c=0$, and $r=0$ or we obtain a similar contradiction for our lower bound. It then also follows we have $m-j$ two entries which are placed independently, and 2 one entries that are placed in the two remaining squares in our row which contains no two entry.

To show $\left(m\mathrm{<mo>\; !\; </mo>}\right)\frac{m\left(m+1\right)}{2}$ is the number of such sets, we will first place the one entries. Note for this assignment there are m rows to choose from that will lack a two entry, and $m\left(\frac{m+1}{2}\right)$ ways to choose the two one placements, given any

row without a two entry. It follows that since we can have no one entry that is adjacent to a two entry since we would have redundancy—for the set would not need the adjacent one entry as opposed to a zero entry—that we can eliminate the two columns and one row with ones in them, and consider the placement of

our twos. Note our placement of ones can be placed exactly $m^2\left(\frac{m+1}{2}\right)$ ways.

Given any placement of our 2 one entries for the case where $j=1$, we have exactly $m-1$ rows and $m-1$ columns on which to assign our two entries, after the one entries have been assigned. Since this can be accomplished exactly $\left(m-1\right)\mathrm{<mo>\; !\; </mo>}$ ways, then we have our total number of Roman dominating sets in our

second class as $m\mathrm{<mo>\; !\; </mo>}\left(\frac{m\left(m+1\right)}{2}\right)$. Summing those in both the classes of Roman

dominating sets proves the theorem. Figure 3 will illustrate an example of a minimum roman dominating set, where $n=m+1$, in the second class of solutions. $\square$

Theorem 5. For the $m\times n$ rook’s graph, with $n>m+1$, the number of minimum roman dominating sets is $n^m$.

Proof: In similar way as in Theorems 3 and 4, we see that we are forced to have exactly m two entries, with one placed in each row. Since there are m rows, and n ways to pick a square in each row, then we have our total of $n^m$ ways to pick our m two entries. $\square$

3. The Roman Domination Number on the Bishop’s Graph and the Count for Odd n

Theorem 6. For odd $n\ge 3$, ${\gamma }_r\left(B_n\right)=2n-1$ and the number of distinct, minimum roman dominating sets is $4\left(\frac{n-1}{2}\right)\mathrm{<mo>\; !\; </mo>}\left(\frac{n-3}{2}\right)\mathrm{<mo>\; !\; </mo>}$.

Proof: We will begin the proof by providing a roman dominating set of cardinality $2n-1$, namely by associating twos with every square in the center-most row—save for the left-most square in this row which is associated with a one. All other squares are associated with zeros. This provides a roman dominating set of cardinality $2n-1$ for odd n, thus providing the upper bound of ${\gamma }_r\left(B_n\right)\le 2n-1$.

To see the rest of the proof we must describe all our possible sets of minimum roman dominating sets by breaking our $n\times n$ board up into six regions, and

Figure 3. Again, let the rooks represent two entries and let the pawns represent one entries. Then this figure represents a minimum roman dominating set, with $n=m+1$, in the second class of possible solutions.

applying the pigeonhole principle to eliminate certain placements. Then, the placements that remain will be shown to all have roman cardinality of $2n-1$, whereas the eliminated placements will all have roman cardinality of greater than $2n-1$. We will then show independence among all our one and two entries, beyond the limitation of regional placement. Then the count will be given of all sets of roman dominating sets with these properties which will be shown to be sufficient for a minimum roman dominating set on the bishop’s graph.

First take the origin to be the center of the center-most square, and each square identified by the coordinates at the center of its square. Then, begin by labeling the squares that lie on sum diagonals having the sum of the coordinates

exclusively between $\frac{n-1}{2}$ and $\frac{3\left(n-1\right)}{2}$, and also difference diagonals with the difference of the coordinates having values exclusively between plus and minus $\frac{n-1}{2}$ we will label as Region one. These squares form the center-most squares in the sense that the associated coordinates of these squares are all within an inclusive grid distance of $\frac{n-1}{2}$ of the center-most square.

Region two squares consist of the squares that fall on a difference diagonal having the exact difference of the coordinates ( $y-x$ ) of these squares as either

plus or minus $\frac{n-1}{2}$, but isn’t on the edge of our $n\times n$ board. Region three squares consist of the squares laying on the diagonal having a sum of the coordinates of these squares of value $\frac{n-1}{2}$ or $\frac{3\left(n-1\right)}{2}$, but again are not on

the edge of our $n\times n$ board. Region four consists of these 4 border squares excluded in both Region two and Region three—the middle squares in the left- and right-most columns, and also, the middle squares in the top and bottom-most rows.

Region five is the region whose squares have sums of the coordinates associated with these squares either strictly less than $\frac{n-1}{2}$, or strictly greater than $\frac{3\left(n-1\right)}{2}$, with the difference ( $y-x$ ) of any of these associated coordinates falling exclusively between plus and minus $\frac{n-1}{2}$. Region six is the final set of

remaining squares, with the difference of the coordinates of any of these individual squares ( $y-x$ ) having a value not inclusively between plus or minus

$\frac{n-1}{2}$, but having sum of the coordinates fall exclusively between $\frac{n-1}{2}$ and $\frac{3\left(n-1\right)}{2}$. Figure 4 will illustrate.

We will now define a set of variables used to lay out an argument that “pigeon-holes” the placement of two entries, by contradiction, to Regions one and four solely—namely $n-2$ two entries in Region one, and 1 two entry in Region four. Also, a lone one entry will be placed in Region four. Define $R_1$, $R_2$, $R_3$,

Figure 4. Squares occupied with black pawns make up region one squares. Squares occupied with white bishops are Region two squares. Squares occupied with dark bishops make up Region three squares. Region four squares are occupied by white pawns. Regions five and six are formed by the unoccupied squares, as labeled above.

$R_4$, $R_5$, and $R_6$ as the number of two entries associated with Regions one through six, respectively. Also, label the number of one entries as o.

Set $R_1=n-2-a$, for some whole number a. First we note that if either $a>R_5+R_2$ or $a>R_6+R_3$, then $a-2\le R_2+R_5$ and $a-2\le R_3+R_6$, for if not we would have at least 3 squares in Region one not adjacent to a two entry that are all on a common diagonal. This is a contradiction since the placement of an additional two entry (as opposed to the minimum of three, one entries needed to saturate these squares) in this diagonal, beyond those placed, would further decrease our roman cardinality. Note also that it is not possible for either $a>R_5+R_2$ or $a>R_3+R_6$, for if either, without loss of generality, then $R_5+R_2=a+1$ clearly or the cardinality of the Roman dominating set is greater than $2n-1$. For the case where $R_5+R_2=a+1$ there would need to be either an additional two placement in either Regions three or region six, or, at least two one placements in Region six—since there would be an open difference diagonal among the diagonals that have difference $y-x$ between plus and

minus $\frac{n-1}{2}$. This would put ${\gamma }_R\left(B_n\right)\ge 2n$, a contradiction.

For the case where $R_5+R_2=a$ (or $R_3+R_6=a$ without loss of generality), note we have all four Region four squares unsaturated. Note also we’re limited to only at most a single two entry in Regions two, three, or four without the cardinality of our Roman dominating set exceeding $2n-1$. Also note the only squares adjacent to these Region four squares are in Regions two, three, and four and that a placement of an additional two entry in Regions two or three only saturates exactly two of these Region four squares. It then follows that we must place an additional two entry in Region four. This leaves us with exactly one unsaturated Region four square. Since no additional two entries are allowed for the Roman dominating set to be of minimum cardinality, we associate a one entry with this square. However, we still have at least two unsaturated squares in Region six which implies the set is not a Roman dominating set.

For the case where $a-2\le R_2+R_6<a$ and $a-2\le R_3+R_5<a$, with $R_1=n-2-a$, assume $R_2+R_6=a-2=R_3+R_5$. If we assume then that $a>3$, we then note that $2a>7$. Note then since $R_2+R_6=a-2=R_3+R_5$, and $R_1=n-2-a$, then there are exactly four squares in Region one that are not adjacent to any two entry. Thus $o\ge 4$. Thus $2a+2R_4+o>11$, or $2\left(n-2-a\right)+4\left(a-2\right)+2R_4+o>2n-1$. But since ${\gamma }_r\left(B_n\right)\ge 2\left(n-2-a\right)+4\left(a-2\right)+2R_4+o$, then we have a contradiction.

Next assume $a=3$. Then $R_2+R_6=1=R_3+R_5$. For this assumption there are three cases to consider. For the case where $R_6=1=R_5$, it follows that $2R_4+o\ge 8$. This comes from the fact that we require at least four one entries in Region one and beyond this either four one entries in Region four, along with two entries in Regions two, three, or four, or a lone two entry and two one entries in Region four. With this note that if $R_4=1$ under this case $o\ge 6$, since placing only the sole two entry in Region four leaves us with two needed one entries in Region four and the four one entries in Region one. Finally, if $R_4=0$, then $o\ge 8$, since we would have four needed one entries in both Regions one and four. So note now since $2R_4+o\ge 8$, $a=3$, and $R_6=1=R_5$, then ${\gamma }_R\left(B_n\right)\ge 2\left(n-5\right)+4+2R_4+o=2n+2>2n-1$, and we have a contradiction.

A similar contradiction arrives for the case where $a=3$ and $R_6=R_3=1$ (which is equivalent, without loss of generality, to the case where $R_2=1=R_5$ and $a=3$ ) in that $2R_4+o\ge 6$. This is arrived at by assuming one of $R_4=0$, $R_4=1$, or $R_4>2$. For the case with $R_4=0$, we have $o\ge 6$ (at least four one entries in Regions one and at least two one entries in Region five). For the case with $R_4=1$, we have $o\ge 4$ (at least four one entries in Region one). Lastly the case for which $R_4>2$ we have $o\ge 4$ (at least four one entries in Region one). Thus it follows that for the case where $a=3$, $2R_4+o\ge 6$. Thus, for $a=3$, ${\gamma }_r\left(B_n\right)\ge 2R_1+2\left(R_2+R_3+R_5+R_6\right)+2R_4+o\ge 2\left(n-5\right)+4+6=2n>2n-1$, a contradiction.

Next consider the case where $a=2$, and $R_2+R_6=a-2=R_3+R_5$. Thus $R_2=R_3=R_5=R_6=0$. It then follows that either $R_4=0$ (in which case at least 4 one entries are needed in Regions one, four, five and six, for a total of at least 16 one entries), $R_4=1$ (in which case at least 4 one entries are needed in Regions one, five, and six, and a single one entry in Region four for a total of at least 13 one entries), or $R_4=2$ (in which case at least 4 one entries are needed in each of Regions one, five, and six for a total of at least 12 one entries) since if $R_4>2$ we still need at least twelve one entries in Regions one, five and six. Thus, for this case, $2R_4+o\ge 15$. Thus we arrive at the following contradiction, ${\gamma }_R\left(B_n\right)\ge 2\left(n-4\right)+2R_4+o\ge 2n+7>2n-1$.

Next let us assume the following subcase: $R_2+R_6=a-1$ and $R_3+R_5=a-2$ (or $R_3+R_5=a-1$ and $R_2+R_5=a-2$, without loss of generality by symmetry). Note first if $a>4$ for this subcase then we arrive at a contradiction, since ${\gamma }_R\left(B_n\right)=2\left(n-2-a\right)+2\left(2a-3\right)+2R_4+o>2n-1$ for $a>4$. Thus, assume first $a=4$. This easily leads to contradiction as well since we need at least two one entries in Region one, and ${\gamma }_R\left(B_n\right)\ge 2R_1+2\left(R_2+R_3+R_5+R_6\right)+2R_4+o=2\left(n-6\right)+10+2R_4+2>2n-1$.

Next assume $R_2+R_6=a-1$ and $R_3+R_5=a-2$, with $a=3$. Note first we require at least two one entries in Region one for all the upcoming subcases. For the first subcase assume $R_2=2$, with $a=3$, $R_2+R_6=a-1$, and $R_3+R_5=a-2$. For this subcase note that there are at least two unsaturated Region six squares. It follows then for this subcase that $2R_6+o\ge 4$. Thus we have ${\gamma }_R\left(B_n\right)\ge 2\left(n-5\right)+2\left(3\right)+2R_6+o>2n-1$, a contradiction.

Next assume $R_2=1$, with $R_6=1$, $R_3+R_5=1$, and $a=3$. Thus $2R_4+o\ge 4$ since there are at least two one entries needed in Region one, as noted previously, and two unsaturated Region four squares. Thus ${\gamma }_R\left(B_n\right)\ge 2\left(n-5\right)+6+4>2n-1$, a contradiction. Thus, for the final subcase assume $R_2=0$ with $R_6=2$, $R_3+R_5=a-2$, with $a=3$. So, then $2R_4+o\ge 5$, since as noted previously we have the two unsaturated Region one squares and the four unsaturated Region four squares. Also for this subcase note that ${\gamma }_R\left(B_n\right)\ge 2\left(n-5\right)+6+5>2n-1$, a contradiction.

Note for the case for which $a=2$, $R_2+R_6=a-1$, and $R_3+R_5=a-2$, $o\ge 7$. This follows since there must be one entries to cover a minimum of seven unsaturated squares - two in Region one, one in Region six, and at least four in Regions three and five. This leads to a contradiction as well since it follows that ${\gamma }_R\left(B_n\right)\ge 2\left(n-2-a\right)+2\left(R_3+R_4+R_5\right)+2\left(R_2+R_6\right)+o\ge 2n+1>2n-1$.

Next assume $R_2+R_6=a-1=R_3+R_5$, with $R_1=n-2-a$. Note that if $a>3$, we have ${\gamma }_R\left(B_n\right)\ge 2\left(n-2-a\right)+4\left(a-1\right)+o>2n-1$, a contradiction. Assume now $a=3$. Note for this case $2R_4+o>1$ unless $R_2=2=R_3$, since there is at least one Region one square left unsaturated regardless, and at least one unsaturated Region four square after the placement of twos in all Regions but four. This yields ${\gamma }_R\left(B_n\right)\ge 2\left(n-5\right)+8+2R_4+o>2n-1$, a contradiction. Thus if $R_2+R_6=2=R_3+R_6$ with $R_1=n-5$, then $R_2=2=R_3$. So assume $R_2+R_6=2=R_3+R_6$ with $R_1=n-5$ and $R_2=2=R_3$. Then $o>2$, since there will be at least two squares in each of Regions five and six and at least one square in Region one left unsaturated after these placements. Thus ${\gamma }_R\left(B_n\right)\ge 2\left(n-5\right)+8+3>2n-1$, a contradiction.

So to eliminate our final possibility of placement by region solely, assume $R_2+R_6=1=R_3+R_5$ and $R_1=n-4$. There are three subcases by symmetry. In the first subcase assume $R_2=R_3=1$. Thus $o\ge 5$ since there will be at least two unsaturated squares in each of Regions five and six, and a lone unsaturated square in Region four. Thus ${\gamma }_R\left(B_n\right)\ge 2\left(n-4\right)+4+5=2n+1>2n-1$, a contradiction.

For the next subcase assume either $R_2=1=R_5$ (or without loss of generality, by symmetry, $R_3=R_6=1$ ). Note for this subcase $o\ge 5$, since there are at least four unsaturated squares in Region six and one in Region one after all placement of two entries. Thus ${\gamma }_R\left(B_n\right)\ge 2\left(n-4\right)+4+5=2n+1>2n-1$, a contradiction. For the final subcase, where $R_5=R_6=1$ with $R_1=n-4$, note $2R_4+o\ge 5$ since the four Region four squares all remain unsaturated along with a Region one square after placement of all twos in Regions one, two, three, five, and six. This leads to ${\gamma }_R\left(B_n\right)\ge 2\left(n-4\right)+4+5=2n+1>2n-1$, a contradiction.

This leads us to the only possible placement, with $n-2$ two entries placed in Region one, a lone two entry in Region four, and a one entry placed in Region four on the opposite border as the other entry in Region four. It is easy to see these entries must all be independent, for if not we have unsaturated squares after placement. To see this restriction by region, and independence of the entries, it is sufficient for the set to be a minimum roman dominating set, first note its’ cardinality is indeed $2n-1$. Also note the squares in Regions one, two, and six all lay on exactly $n-2$ sum diagonals. Likewise, the squares in Regions one, three, and five all lay on exactly $n-2$ difference diagonals. Thus, if placed independently in Region one, the $n-2$ two entries should be provided adjacency for all vertices corresponding to squares in all regions, excluding Region four. Also, a one entry and a two entry, if placed independently in Region four, would either provide adjacency for all Region four squares/vertices or would be occupied by a one entry.

Finally, we count the number of such minimum roman dominating sets by noting that the subgraph associated with the squares in Region one is isomorphic to the union of $R_{\frac{n-1}{2}}$ and $R_{\frac{n-3}{2}}$. Thus, since there are exactly four ways to

place the entries independently in Region four and $\frac{n-1}{2}\mathrm{<mo>\; !\; </mo>}\frac{n-3}{2}\mathrm{<mo>\; !\; </mo>}$ ways to place the entries independently in Region one, we have the proof. $\square$

4. Total Domination Section

Theorem 7. The count on the number of minimum total dominating sets for the $n\times n$ bishop’s graph is ${\left(\frac{\frac{n-1}{2}\mathrm{<mo>\; !\; </mo>}}{\frac{n-1}{6}\mathrm{<mo>\; !\; </mo>}\times 2^{\frac{n-1}{6}}}\right)}^2$ for the subgraph associated with

the light squares when $n\equiv 1\left(\mathrm{mod}12\right)$ (with $n>1$ ) and the same for the subgraph associated with the dark squares when $n\equiv 7\left(\mathrm{mod}12\right)$.

Proof: Begin by breaking the subgraph associated with the light squares when $n\equiv 1\left(\mathrm{mod}12\right)$ into three separate regions (the case for the dark squares when $n\equiv 7\left(\mathrm{mod}12\right)$ is equivalent). Similar to the methods found in Section 3, above, label Region one as the light-colored squares having sum of their coordinates at

the center of the square exclusively between plus and minus $\frac{n-1}{2}$ and the difference of their coordinates ( $y-x$ ) also exclusively between plus and minus $\frac{n-1}{2}$ (with the origin take as the center of the center-most square of our $n\times n$ board). Label Region two squares as the light colored squares having sum values in this manner not exclusively between plus and minus $\frac{n-1}{2}$, but difference values exclusively between plus and minus $\frac{n-1}{2}$. Finally, label Region three as the light colored squares having sum values exclusively between plus and minus $\frac{n-1}{2}$ and having difference values not exclusively between plus and minus $\frac{n-1}{2}$.

Next let us define a subgraph G similar to the subgraph G found in both [12] [13], except we are defining it for the bishop’s graph and not the queen’s graph. So given the total dominating set of vertices associated with the occupied squares, we define G to contain only the set of vertices associated with the total dominating set. Two vertices are then adjacent in G if and only if their corresponding squares (which are occupied by bishops) are attacked along unoccupied squares. Note if there is at most two bishops in any given diagonal there is no difference between G and the subgraph induced by the vertices associated with the occupied squares. It is only when there are three or more bishops in a given diagonal that a difference arises. For example, note that the subgraph induced by vertices associated with occupied squares in the same diagonal will form a complete graph, whereas in G these same vertices form a path. Then define $d_p$ and $d_n$ as the number of positive-sloping and negative-sloping diagonal edges for the graph G.

We then set $R_1+R_2-c=\frac{n-1}{2}-a$ and $R_1+R_3-r=\frac{n-1}{2}-b$, for some

non-negative integers a and b with $R_1$, $R_2$, and $R_3$ taken as the number of light squared bishops in Regions one through three, c as the number of positive diagonal edges in the subgraph G between bishops either in Regions one or two, and r as the number of negative diagonal edges in the subgraph G between bishops either in Regions one or three. Note it is the case that $c\le d_p$ and $r\le d_n$.

It then follows that either a or b is zero, since if not we would have a light-colored square in region one not under attack. Without loss of generality, by symmetry, take $a=0$. It also follows that there is no empty negative sloping diagonal that has the sum of its coordinates exclusively between plus and minus

$\frac{n-1}{2}$. It then follows that $r=d_n$, for if we had a negative diagonal edge

between two light-colored bishops, both in Region three, then both would be adjacent to light-colored bishops in Region one along positive diagonals. This would then make either redundant, since both would be adjacent to a light-colored bishop along positive and negative diagonals. In a similar type manner $c=d_p$.

Next we will show that the unsaturated squares remaining in Region three after placing Region one and Region two bishops require $R_3\ge b$. In the upper-left

part of Region three note that we have at least $\lceil \frac{b}{2}\rceil$ positive diagonals

containing unsaturated squares after Region one and Region two bishops have been placed, and at least the same number in the bottom-right part of Region three. It follows that because these unsaturated squares lie on negative diagonals unoccupied by bishops, that they must be dominated along the positive diagonals in Region three. Thus, since there are at least b of these diagonals not fully saturated, then $R_3\ge b$.

Back to the beginning of the proof with the new information we obtain by substitution $R_1+R_2-d_p=\frac{n-1}{2}$ and $R_1+R_3-d_n=\frac{n-1}{2}-b$. Summing these

we obtain $R_1+{\gamma }_t\left(L_n\right)-\left(d_p+d_n\right)=n-1-b$, with ${\gamma }_t\left(L_n\right)$ being the total domination number of the subgraph formed by the light-colored squares of the bishop’s graph for $n\equiv 1\left(\mathrm{mod}12\right)$. But it follows that since the set of bishops is a total dominating set and has no isolates, then G can have no isolates. Thus, since G can have no isolates and $d_p+d_n$ is the total number of edges in G, then

$d_p+d_n\ge \frac{{\gamma }_t\left(L_n\right)}{2}$. Thus, we obtain by substitution $R_1+\frac{{\gamma }_t\left(L_n\right)}{2}=n-1-b$, or since it has been shown previously that ${\gamma }_t\left(L_n\right)=\frac{2\left(n-1\right)}{3}$, $R_1=\frac{2\left(n-1\right)}{3}-b$. It follows then that $R_1+R_3\ge \frac{2\left(n-1\right)}{3}$. However, since $R_1=\frac{2\left(n-1\right)}{3}-b$ there

remains unsaturated squares in Region two after placing only the bishops in Region one and Region three. Thus $R_2\ge 1$. But then

${\gamma }_t\left(L_n\right)=R_1+R_2+R_3\ge \frac{2\left(n-1\right)}{3}-b+b+1$, a contradiction. It follows then that $b=0$, $R_1=\frac{2\left(n-1\right)}{3}$, $R_2=0$, and $R_3=0$.

To count the number of minimum total dominating sets we will note that every diagonal, both positive and negative, that contains a square in Region one must be occupied. To see this first note every square in Region one must be dominated twice, once along a negative diagonal and once along a positive diagonal, or else we’d have unsaturated squares in either Region two or Region three (depending upon whether we had an open negative or positive diagonal).

Also note that there must be exactly $\frac{n-1}{3}$ row edges in G and the same

number of column edges in G with all the edges between vertices associated with bishops in Region one.

We begin the count by selecting the $\frac{n-1}{3}$ positive diagonals that contain exactly two bishops and the $\frac{n-1}{3}$ negative diagonals that contain exactly two bishops. Note there are exactly $\frac{n-1}{2}$ choose $\frac{n-1}{6}$ ways to choose the positive

diagonals and the same number of ways to choose the negative diagonals. Thus the result is squared.

Next, given the assignment of two adjacent bishops to the positive and negative diagonals in such a way, we note there are $\frac{\frac{n-1}{3}\mathrm{<mo>\; !\; </mo>}}{2^{\frac{n-1}{6}}}$ ways to place the positive

diagonal adjacent bishops given the constraints. We can then square the result, since the number of ways to place the negative diagonal adjacent bishops is the same given the constraints. We then multiply the results of the last two paragraphs, simplify the choose symbols by cancelling, and obtain the answer. $\square$

5. Conclusion

Certainly, a similar method might provide the roman domination number for the square bishop’s graph and the count on the number of minimum roman dominating sets, when n is even. The partition of squares into the six regions indicated in this paper might also provide some use for finding the counts of the remaining cases for the number of minimum total and paired dominating sets on the square bishop’s graph. See both A303144 and A303141 in the Online Encyclopedia of Integer Sequences for some of the values on these counts for very small board sizes. Note the available count for $n=7$ obtained in this paper matches the one found for $n=7$ in the OEIS. It should also be noted that the case solved for the count of the minimum total dominating sets for the light squares when $n\equiv 1\left(\mathrm{mod}12\right)$ (and the dark squares when $n\equiv 7\left(\mathrm{mod}12\right)$ ) was a difficult and lengthy argument. However, the implementation of technology to the problem for the other cases might very well be of benefit—as the author highly suspects the other cases would be longer without other computational means.

Conflicts of Interest

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

References

[1]	Watkins (2004) Across the Board: The Mathematics of Chessboard Problems. Princeton University Press, Princeton and Oxford.
[2]	Chaluvaraju, B. and Chaitra, V. (2012) Roman Domination in Complementary Prism Graphs. International Journal of Mathematical Combinatorics, 2, 24-31.
[3]	Cockayne, E.J., Dreyer Jr., P.A., Hedetniemi, S.M. and Hedetniemi, S.T. (2004) Roman Domination in Graphs. Discrete Mathematics, 178, 11-22.
[4]	Favaron, O., et al. (2009) On the Roman Domination Number of a Graph. Discrete Mathematics, 309, 3447-3451.
[5]	Fu, X.L., et al. (2009) Roman Domination in Regular Graphs. Discrete Mathematics, 309, 1528-1537.
[6]	Henning, M.A. and Hedetniemi, S.T. (1998) Defending the Roman Empire—A New Strategy. Discrete Mathematics, 266, 239-251.
[7]	Henning, M.A. (2003) Defending the Roman Empire from Multiple Attacks. Discrete Mathematics, 271, 101-115.
[8]	Pushpam, P.R.L. and Malini Mai, T.N.M. (2000) Roman Domination in Unicyclic Graphs. Journal of Discrete Mathematical Sciences and Crytography, 15, 201-213.
[9]	Muddebihal, M.H., Basavarajappa, D. and Sedamkar, A.R. (2010) Roman Domination in Line Graphs. Canadian Journal on Science and Engineering Mathematics, 1, 69-79.
[10]	Cockayne, E.J., Gamble, B. and Shepherd, B. (1986) Domination Parameters for the Bishop’s Graph. Discrete Mathematics, 58, 221-227.
[11]	Henning, M.A. and Yeo, A. (2013) Total Domination in Graphs. Springer-Verlag, New York.
[12]	Burchett, P.A. (2005) Paired and Total Domination on the Queen’s Graph. MS Thesis, East Tennessee State University, Johnson City.
[13]	Burchett, P.A. (2006) Paired, Total and Connected Domination on the Queen’s Graph. Congressus Numerantium, 178, 207-222.