Queen Labelings

Queen Labelings Gary Bloom1, Michael Lampis1, F. A. Muntaner-Batle2, and M. Rius-Font3 1Graduate Center, City University of New York 2Facultat de Ci`encies Pol´ıtiques i Jur´ıdiques Universitat Internacional de Catalunya 3Departament de Matem´atica Aplicada IV Universitat Polit`ecnica de Catalunya Abstract. We introduce and investigate the concept of Queen labeling a digraph and its connection to the well-known n-queens problem. In the general case we obtain an upper bound on the size of a queen graph and show that it is tight. We also examine the existence of possible forbidden subgraphs for this problem and show that only two such subgraphs exist. Then we focus on specific graph families: First we show that every star is a queen graph by giving an algorithm for which we prove correctness. Then we show that the problem of queen labeling a matching is equivalent to a variation of the n-queens problem, which we call the rooks-and-queens problem and we use that fact to give a short proof that every matching is a queen graph. Finally, for unions of 3-cycles we give a general solution of the problem for graphs of n(n−1) vertices. 1 Introduction In 1848, the German chess-player Max Bezzel, proposed the 8-queens puzzle. This puzzle consists on putting eight queens on an 8×8-chess board in mutually non-attacking positions, using the standard chess queen’s movement. In other words,the 8-queens puzzle consists of placing 8 queens on an 8 ×8-chessboard, in such a way that no two queens share the same row, column or diagonal. The first solution of the 8-queens puzzle was given in 1859 by Franz Nanck, who also extended the puzzle, to what is known today as the n-queens puzzle, where the objective is to place nqueens in mutually non-attacking position on an n×nboard. This problem has been studied by many mathematicians over the years, including Gauss and Cantor, and the problem of counting how many solutions of the n×n-queens problem exist has become a very challenging and in general unsolved problem in combinatorics. Motivated by the n-queens problem we define the following graph labeling problem: Definition 1. Let G(V,E) be a digraph, possibly with loops. A queen labeling of G(V, E)is a bijection l:V→ {1,...,|V|} such that for every pair of edges (u1, v1),(u2, v2)∈Ewe have l(u1) + l(v1)6=l(u2) + l(v2)and l(u1)−l(v1)6= l(u2)−l(v2). If a digraph Gadmits a queen labeling we say that Gis a queen graph. We call these labelings queen labelings due to a correspondence between solutions to the n-queens problem and queen labelings of 1-regular digraphs. Proposition 1. There exists a bijection between the solutions of the n-queens problem and the queen labelings of the 1-regular digraphs of order n. Proof. Let Qbe a queen labeling of a 1-regular digraph of order n,D, and assume that each vertex takes the name of its label. Then the adjacency matrix of D,A(D), is a solution to the n-queens problem since: 1. Since Dis a 1−regular digraph it follows that in each row and in each column of A(D) we have exactly one 1 2. Since Q(u) + Q(v) is different from Q(x) + Q(y) if (u, v)6= (x, y), it follows that every counter main diagonal contains at most one 1. 3. Since Q(u)−Q(v) is different of Q(x)−Q(y) if (u, v)6= (x, y), it follows that every main diagonal contains at most one 1. Therefore if we replace the 1’s by Queens, we obtain a solution of the n-queens problem. It is clear that two different queen labelings produce two different queen solutions. Now, let Qbe a solution of the n-queens problem. It is clear that each row of the n×ncheesboard contains exactly one queen and each column also contains exactly one queen. Also no main diagonal contains more than one queen and no counter diagonal contains more than one queen either. Therefore if we view Qas an n×nmatrix, where the queens have been replaced by 1’s, this is the adjacency matrix of a 1-regular digraph of order n, labeled with a queen labeling, namely Q. It is clear that if Qand Q0are two different solutions of the n−queens problem, then the labeling obtained by Qand Q0are different. This proves that there is a bijection between the solutions of the n-queens problem and the queen labelings of 1-regular digraphs of order n.  Queen labelings are a variation of the difference and sum labelings which have appeared in various forms in the literature over time. The most well-known variant is probably graceful labelings. For more information on this vast area of research the reader is referred to the excellent (and dynamic) survey [1] and the references therein. In the rest of this paper we will use the term queen graph to refer to a graph which admits a queen labeling. Since all the topics we discuss concern digraphs we will also use the term digraph and graph interchangeably. Unless stated otherwise, we will assume that it is possible for our digraphs to have self-loops. The rest of this paper is organized as follows: in Section 2 we give some general propositions about queen graphs. In Section 3 we prove that all stars are queen graphs. In Section 4 we focus on the problem of queen labeling a set of independent directed edges and in Section 5 we consider the problem in unions of 3-cycles. Section 6 contains some conclusions and open problems. 2 2 General observations regarding queen graphs 2.1 Forbidden subgraphs An interesting question to work on is to characterize the set of queen graphs. The following are two simple observations about the queen graphs: Proposition 2. 1. Every queen graph contains at most one loop. 2. Queen graphs do not contain cycles of length 2(that is to say, two edges with the same endpoints and opposite orientation) Proof. A queen graph cannot have two self-loops because the difference 0 would appear twice. Also, we cannot have two edges with the same endpoints because inevitably the labels would have the same sum.  Observations of this type are often useful when trying to show that a graph is not a queen graph without exhausting all possible labelings. Therefore, it makes sense to study the question of whether there exist other forbidden (induced) subgraphs beyond the 2-cycle and the two self-loops, that is graphs Hsuch that showing that His a subgraph of a graph Gwould imply that Gis not a queen graph. Giving a positive answer to this question would help us to find a better characterization of the family of queen graphs. First, observe that by the definition of forbidden subgraph given above, if His a forbidden subgraph so is every supergraph of H. Therefore, what we are most interested in is minimal forbidden subgraphs, that is, forbidden subgraphs Hsuch that no (proper) subgraph of His also a forbidden subgraph. It is clear that both of the cases pointed out so far are indeed minimal. We will show that none other exist. Proposition 3. The only minimal forbidden subgraphs for queen labeling are the two-cycle and the graph with two self-connected vertices. Proof. Suppose that we want to find a third case of minimal forbidden subgraph H. Clearly Hcannot contain a 2-cycle or two self-loops, otherwise it’s not minimal. Suppose that such an Hexists and it has nvertices. Then there exists a tournament on nvertices H0with a self-loop on exactly one of them which is a supergraph of H. If His a forbidden subgraph, so is H0. We will show that this is not the case. Label the self-connected vertex of H0with 1. Label the other vertices with distinct powers of 2, from 2 to 2n−1. It is not hard to see that this labeling does not repeat any sums or differences. First, the self-loop has a sum of 2 and a difference of 0, neither of which appears anywhere else. Then, every other edge incident on 1 has an odd sum and difference, while the rest of the edges have even sums and differences. Similarly, edges incident on 2 have sums and differences not divisible by 4 and so on. Therefore, there exists a graph G(V, E) which is a supergraph of H0: simply take H0and add enough isolated vertices so that the graph has order 2n−1. This implies that H0is not a forbidden subgraph. 3  2.2 Size of queen graphs One of the first observations that one could make about queen labelings is that the more edges a graph has the harder it is to queen label it. The reason this happens is that more edges add more constraints (we have to make sure that they all have distinct sums and differences) without giving us more labels to use (recall that the set of labels is always {1,...,|V|}. More formally we could say that it is easy to prove that if G(V, E) is a queen graph then any graph G0(V, E0) with E0⊆Eis also a queen graph. This naturally leads to the question of whether we can bound |E|by a function of |V|. The answer is given in the following proposition. Proposition 4. If G(V, E)is a queen graph then |E| ≤ 2|V| − 2. Proof. Suppose that Ghas no self-loops. Let lbe a queen labeling of G. Then the function l(u) + l(v) can only take values in the set {3,...,2n−1}. This set has size 2n−3. Therefore, the graph cannot have more than 2n−3 edges (excluding self-loops) because by pigeonhole principle two would have the same sum. Using the previously made observation that a queen graph has at most one self-loop (otherwise the difference 0 is found twice) we conclude the proof.  The previous proposition uses an argument on the number of different sums available only. A similar argument could be made on the number of available differences. This begs the question of whether there is a way to argue about both at the same time and thus find a better upper bound on |E|. The answer is negative, as implied by the existence of a graph for which the bound is tight. The graph is constructed as follows: for nvertices add edges from 1 to every vertex (including itself) and from nto every other vertex (excluding 1). It is not hard to see that this is a queen graph: all the edges originating from nhave a positive difference, while the rest have negative. All the edges incident to n have sum > n while the rest have ≤n. An example of such a graph is given in Figure 1. 1 2 3 4 5 6 7 8 Fig. 1. An example of the family of densest queen graphs 4 3 Queen labelings for stars In this Section we present a simple algorithm to queen label a star, that is a digraph whose underlying undirected graph is a star. Our algorithm labels the central vertex with the highest label nand then sequentially labels every other vertex starting from the predecessors of the central node. Proposition 5. Every star is a queen graph. Proof. Place the label non the central node. Label the leaves arbitrarily {1, . . . , n− 1}. This is a queen labeling: no sum is repeated because every edge is incident on nand therefore the sum on each edge is equal to nplus the label of its other endpoint. Every edge directed to the central node has a distinct difference from other edges directed to the central node for the same reason. The same applies to edges directed away from the central node. Finally, observe that edges in the first group have negative differences, while in the second positive.  4 Queen labelings for matchings In this Section we focus on matchings, that is simple graphs which consist of a collection of directed edges with distinct endpoints. Consider a matching with 2nvertices, that is nedges. Following the corrsepondence with the n-queens problem, for a matching we have to place nqueens (as many as the edges) on a 2n×2nboard (the adjacency matrix of the graph). However, this correspondence does not immediately give a solution. The reason is that, even though every legal placement of nqueens on a 2n×2nboard does correspond to a queen labeling of some graph with 2nvertices and nedges, it does not necessarily correspond to a labeling of a matching. For example, in the queens game it is legal to place a queen on the main diagonal, while a matching does not have self-loops. However, the chess formulation of the problem is often very helpful in analysis. In order to be able to use it in this case we define the following problem: Definition 2. The n-rooks-and-queens problem is the problem of placing nrooks and nqueens on a 2n×2nchess board so that 1. If a queen is placed in position (i, j)a rook must be placed in position (j, i). 2. No queen is attacked by any other piece. Proposition 6. There is a 1-1 correspondence between solutions to the n-rooks- and-queens problem and the queen labelings of a matching with 2nvertices. 5 Proof. Suppose that we have a solution to the n-rooks-and-queens problem. If we consider it as an adjacency matrix with the queens replaced by 1’s then we get a queen labeled directed graph (otherwise one of the queens would be attacked in the original solution). To see why this graph is a matching consider some row iand the corresponding column iof the board. There is at most one queen in both the row and the column, because a queen in row iimplies the existence of a rook in column iwhich rules out the placement of another queen on that column. Therefore, every vertex of the graph has total degree at most 1. It is not hard to see that no vertex can have total degree 0, otherwise we would have to place 2npieces on a (2n−1) ×(2n−1) board which is impossible. Therefore, the graph is a matching. For the other direction, if we take the adjacency matrix of a queen labeled matching and place queens in the place of the 1’s we get a board where no queen attacks another. Furthermore, if the adjacency matrix had a 1 in (i, j) it had only 0 in column iand row j(since the graph is a matching). Therefore, placing a rook in (j, i) will still not attack any queen.  Using the above game, we propose the following method to queen label any matching of nedges: place nqueens in mutually non-attacking positions in the top-right quadrant of a 2n×2nmatrix (that is in rows 1, . . . , n and columns n+ 1,...,2n). Then, for every queen in position (i, j) place a rook in (j, i). It is not hard to see that this placement guarantees that no queen is attacked and therefore we obtain a labeling for the matching simply by solving an n-queens problem. The only detail left is what happens if no such solution exists, that is n= 2 or n= 3. It is not hard to obtain labelings in these special cases as well, for example for two edges we have 1 →2 and 4 →3, and for three edges we have the labeling 1 →6, 2 →4, 5 →3. Therefore, we can conclude that: Proposition 7. Every matching is a queen graph. 5 Queen labelings for unions of 3-cycles In this Section the graph family we focus on is unions of 3-cycles. First, it is not hard to see that C3is not a queen graph. 2C3is a queen graph and so is 4C3(Figure 2). It is possible to prove that 3C3is not a queen graph. However, the proof is rather tedious and relies on exhausting every possible case. For more than 4 3-cycles the problem becomes quite complicated and hard to attack by hand. Using a computer program we obtain solutions for larger instances. Among the many solutions produced were those of Figure 3 and 4. From them we can obtain an interesting pattern. The pattern is generally followed when the number of vertices is of the form n(n−1). In this case nqueens are placed in the first nrows with distances of n−1 columns between them. Then, this pattern is moved one to the left and repeated. 6 1 2 4 3 6 5 1 3 9 2 6 5 4 12 10 7 8 11 Fig. 2. Queen labelings of 2 and 4 3-cycles Q Q Q Q Q Q Q Q Q Q Q Q Fig. 3. A solution for 4 3-cycles Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Fig. 4. A solution for 10 3-cycles 7 Working analytically we get that a queen is placed in row iat position f(i) with f(i)=(n−1) [(i−1) mod n]+(n−1) −i−1 n Proposition 8. Placing n(n−1) queens in positions (i, f(i)), i ∈ {1, . . . , n(n− 1)}is a solution to the n(n−1)-queens problem. Proof. It is obvious that we get one queen on every row. Now let us show that fis 1-1 and therefore we have one queen on every column. Let us consider some i, i0which we can rewrite as i=kn +l+ 1 for some 0 ≤l≤n−1,0≤k≤n−2 and i0=k0n+l0+ 1. Now f(i) = f(i0)⇒ (n−1)l−k= (n−1)l0−k0⇒nl −(l+k) = nl0−(l0+k0). This gives us l+k≡l0+k0( mod n). This implies that l+k=l0+k0(which gives us i=i0) or |(l+k)−(l0+k0)|=n. But then from the previous equation divided by nwe get that |l−l0|= 1 so |k−k0|=n−1 which is impossible. Therefore, fis 1-1. Suppose that for some i, i0we have i+f(i) = i0+f(i0). Therefore, (n−1) [(i−1) mod n]−i−1 n+i= (n−1) [(i0−1) mod n]−i0−1 n+i0 Let i=kn +l+ 1 for 0 ≤l≤n−1,0≤k≤n−2 and i0=k0n+l0+ 1. We have (n−1)l−k+kn +l= (n−1)l0−k0+k0n+l0⇒ n(k+l)−k=n(k0+l0)−k0 But we know that kand k0are < n. Therefore taking the above equation mod ngives us k=k0which implies l=l0. Finally, suppose i−f(i) = i0−f(i0). Then kn +l−(n−1)l+k=k0n+l0−(n−1)l0+k0⇒ (k−l)n+ (k+ 2l)=(k0−l0)n+ (k0+ 2l0)⇒ (k−l)(n+ 1) + 3l= (k0−l0)(n+ 1) + 3l0 This implies that 3l≡3l0( mod (n+ 1)). Because either nor n−1 is a multiple of 3, n+ 1 cannot be a multiple of 3. Therefore, 3 has an inverse mod (n+ 1) which implies that l≡l0( mod (n+ 1)). This gives us l=l0which implies i=i0.  8 Now what remains to show is that the solution to the n-queens problem which we have constructed is also a solution to our queen labeling problem, or in other words that the adjacency matrix we get corresponds to a union of 3-cycles. Proposition 9. Placing n(n−1) queens in positions (i, f(i)), i ∈ {1, . . . , n(n− 1)}is a solution to the problem of queen labeling a union of n(n−1) 33-cycles. Proof. What we need to prove is that ∀i, f(f(f(i))) = i. Once again, rewrite i as i=kn +l+ 1. Now, suppose that k+l+ 1 < n. We have f(i) = (l+ 1)(n−1) −k=ln −l+n−1−k=ln +n−(k+l+ 1) f(f(i)) = (n−(k+l+ 1))(n−1) −l=n(n−1) −(k+l+ 1)n+k+ 1 f(f(f(i))) = (k+1)(n−1)−(n−1−(k+l+1)) = kn−k+n−1−n+1+k+l+1 = kn+l+1 = i For the case n≤k+l+ 1 <2nwe have f(i)=(l+ 1)(n−1) −k=ln −l+n−1−k= (l−1)n+ 2n−(k+l+ 1) f(f(i)) = (2n−(k+l+ 1))(n−1) −(l−1) = 2n(n−1) −(k+l+ 1)n+k+ 2 f(f(f(i))) = (k+ 2)(n−1) −(2n−2−k−l−1) = kn +l+ 1 = i  6 Conclusions In this paper we studied queen labelings in the general case, giving bounds on the size of queen graphs and in several specific cases, namely stars and matchings (where the problem was solved) and unions of 3-cycles (where we showed how to construct a general solution). Much remains to be done. First, the data we arrived at using computer programs seems to suggest that the problem is always solvable for unions of 3-cycles of any size (with the exception of one and three 3-cycles). It would be interesting to obtain a proof of this, constructive or not. Second, a major gap in our knowledge is a technique for proving that a graph is not a queen graph when the easy bounds fail. So far no other method is known 9