ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 9 (2015) 115-124 Laceable knights Michael Dupuis Univ. of St. Thomas, St. Paul, Minnesota, USA Stan Wagon Macalester College, St. Paul, Minnesota, USA Received 12 December 2012, accepted 17 August 2013, published online 26 August 2014 A bipartite graph is Hamilton-laceable if for any two vertices in different parts there is a Hamiltonian path from one to the other. Using two main ideas (an algorithm for finding Hamiltonian paths and a decomposition lemma to move from smaller cases to larger) we show that the graph of knight's moves on an m x n board is Hamilton-laceable iff m > 6, n > 6, and one of m, n is even. We show how the algorithm leads to new conjectures about Hamiltonian paths for various families, such as generalized Petersen graphs, I-graphs, and cubic symmetric graphs. Keywords: Hamilton-laceable, generalized Petersen graphs, Hamilton-connected, Hamiltonian paths, knight graph, traceable. Math. Subj. Class.: 05C45, 05C85 1 Introduction Let Nm,n be the graph of knight's moves on an m x n chessboard. Knight's tours, which are Hamiltonian cycles in these graphs, have been considered for over 1000 years and in 1991 Allen Schwenk ([13]; see also [5]) characterized the knight graphs having a Hamiltonian cycle. Assuming m < n, he proved that Nm,n is Hamiltonian iff at least one of m, n is even, m is not 1, 2, or 4, and (m, n) is not (3,4), (3, 6), or (3, 8). Two related questions arise: Which knight's graphs are (a) Hamilton-laceable (HL); (b) traceable? A bipartite graph is HL if for any two vertices in different parts there is a Hamiltonian path from one to the other. And a graph is traceable if it has at least one Hamiltonian path. An HL graph with at least one edge is necessarily Hamiltonian. Here we give a complete characterization of the HL knight's graphs: Nm n is HL iff m and n are at least 6 and E-mail addresses: mdupuis@osii.com (Michael Dupuis), wagon@macalester.edu (Stan Wagon) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 116 Ars Math. Contemp. 9 (2015) 115-124 at least one of m, n is even. The problem has been investigated for square boards; Conrad et al. [5] showed that Nn,n is HL iff n is even and n > 6. For traceability, the problem has been solved, though unpublished. Mark Krusemeyer settled it in 1972 (see also [8]). A paper in 1978 by Cull and DeCurtins [6] settles all cases except N3 n and N4,n. The failure of the 4 x 4 case appears in [16, p. 51]. We include here a simple approach to the 3 x n and 4 x n cases. The complete characterization is that the only nontraceable, connected knight graphs are N3,5, N3,6, and N4,4. Our approach uses computation and the algorithms used have broad application to Hamiltonian properties. We discuss some conjectures inspired by connectivity and lace-ability computations on several thousand graphs. 2 Knight graph laceability Our method is similar to that of [5] in that we use computation for small cases and then settle the general case by decomposition into small cases. Using Mathematica's Find-HamiltonianCycle function for the computer search means that the amount of programming is quite small. We use HP to abbreviate Hamiltonian path. Theorem 2.1. Km,n is not HL if m < 5 or both m, n are odd. Proof. By Schwenk's Theorem we need only consider K3,n and K5,n. Those cases follow from the following lemma since the corner vertices satisfy the hypothesis. □ Lemma 2.2. If G is bipartite and Hamiltonian and has two vertices of degree 2 that have exactly one common neighbor, then G is not HL. Proof. Let u and v be the degree-2 vertices with common neighbor w. Let x be the neighbor of u that is not w and let a be a neighbor of x that is not u. Such must exist because the graph is Hamiltonian, and so has no degree-1 vertices. Then a is neither w (because graph is bipartite) nor v (w is the only common neighbor of u and v). There can be no Hamiltonian path from a to w because once a path strikes one of u, v it must go to w and therefore end without visiting both u and v. □ The main tool for the general result is a decomposition lemma, but there is a complication. Let S and F denote the start and finish points of an HP. There is one case — where S and F occupy the rightmost corners of a component board as shown in Figure 1 — where it is not clear that combining two HL boards leads to an HL board. The lemma that follows avoids this case. We say that an m x n board is HL if Km,n is HL; the width of an m x n board is n, the horizontal dimension. Lemma 2.3 (Decomposition Lemma). Suppose the m x n board G splits into two HL boards by a vertical line. Then G is HL provided • m is odd; or • m is even, n is even, and the two component boards have different widths; or • m is even, n is odd, and the two component boards have widths that differ by 2 or more. M. Dupuis and S. Wagon: Laceable knights 117 5 F Figure 1: A difficult case on a 6 x 12 board. m F A C \ .X B- V Y- D n k Figure 2: Building an HP from S to F. Dashed arrows stand for a longer part of a Hamil-tonian path. Proof. Note that m > 6 by Theorem 2.1, so there are at least three white and three black squares in any column. Call the two smaller boards (called halves), each with m rows, left and right. If S and F are in different halves, just take an HP in S's half to an end point near the border, cross over to the F's half, and finish by using an HP in that half to reach F. Suppose S and F are in the same half, say the left, and C and D are the rightmost corners of the left half. If one of C or D is neither S nor F, say C, find an HP in the left from S to F. The path must, just before reaching C, visit A or B, the two neighbors of C. Assume, by switching S and F if necessary, that it first passes through B, the rightmost of A and B. Then break at B, go into the right side to X (see Figure 2), and traverse the right side by an HP from X to Y. Finish by jumping to C and continuing to A and F by the original path. This leaves the troublesome case that S and F occupy the corners C and D; here it is not clear how to build an HP in the large board. Because S and F have opposite colors, m is even. So we can simply divide G vertically but in the other order, leaving S and F where they are. Because of the conditions on the widths of the halves, S and F no longer occupy the two rightmost corner positions of the left half, and the method of the preceding 118 Ars Math. Contemp. 9 (2015) 115-124 Figure 3: A resolution of the single troublesome case for K6,12. paragraph applies. □ The next result is based on an algorithm for finding HPs. Several of these cases were first done in [5], and even before that Schwenk worked out the K8,8 case by hand. Using Mathematica, the verification of all 18 cases took about 24 minutes. Theorem 2.4. Km,n is HL whenever (m, n) e {(7,8), (7,10), (9,10)} or m is 6, 8, 10, or 12 and 6 < m < n < 13. Proof. Assume (proof by computation follows) that K6,6, K6,8, and K6,io are HL. Then their doubles (transposing as necessary) — 6 x 12, 8 x 12, 10 x 12 — can be handled by dividing the board in half vertically. Laceability follows from the proof of the decomposition lemma except in the case that S and F occupy the two right-hand corners of the left half. But those cases are easily handled computationally by a search for a single HP, using the algorithm described shortly; the case of 6 x 12 is shown in Figure 3. And having K6,6, we can resolve K 12,12. This is because the 12 x 12 board can be bisected vertically into 12 x 6s, and the decomposition proof takes care of all cases except S and F occupying the rightmost corners of the left half. But then we can divide the board horizontally into two 6 x 12s, which places S and F in different halves and allows the proof of the decomposition lemma to be applied. Also, having 6 x 13 (proof below) yields 12 x 13 by direct application of decomposition. The remaining 18 cases are 6 x 6, 6 x 7, 6 x 8, 6 x 9, 6 x 10, 6 x 11, 6 x 13, 7 x 8, 7 x 10, 8 x 8, 8 x 9, 8 x 10, 8 x 11, 8 x 13, 9 x 10,10 x 10,10 x 11, and 10 x 13. These are handled by finding a complete set of HPs. The square cases were done in [5], but we can take care of all cases with about 18 minutes of computation. Here is an algorithm based on Mathematica's fast FindHamiltonianCycle function. Hamiltonian path algorithm Input: Graph G and two vertices S, F. Output: TRUE if there is a Hamiltonian path in G from S to F; FALSE otherwise. Step 1. Form graph H from G by adding a new vertex v and the edges v ^ S and v ^ F. M. Dupuis and S. Wagon: Laceable knights 119 Step 2. Use a Hamiltonian-cycle finder to check if such a cycle exists in H. This algorithm is quite simple and settles the 18 cases of Theorem 2.4 in 24 minutes. There is no need to apply it to all pairs (S, F) from the two parts. One can restrict S to orbit representatives under the automorphism group. Using a fast algorithm for graph isomorphism, one can add leaves to each of two vertices to determine if they are in the same orbit. When working with larger graphs having a lot of symmetry, this use of orbit representatives cuts down the computation time dramatically. □ The algorithm above was suggested by a referee. Our original algorithm was a little more complicated and can provide more speed in some cases. One can add edge S ^ F to the graph if it is not there already, and then consider, one at a time, the other edges leaving S, checking to see if there is a Hamiltonian cycle that uses that edge. By putting a time constraint on this search one avoids possible dead ends without examining all the possibilities. For many HC or HL graphs this leads to a faster algorithm; in essence, it is a way of tweaking whatever Hamiltonian cycle finder one is using. Another idea that is sometimes useful when the time limit runs out without a path being found is to permute the graph and try again. The idea of using permutations to speed up graph algorithms has been fruitful in other areas, such as the 4-coloring of planar graphs efficiently [8]. The Hamilton cycle algorithm used by Mathematica has several cases, but a main one is the Angluin-Valiant heuristic. For larger problems one can use traveling salesman problem software to search for Hamiltonian cycles (see §5). Theorem 2.5. Nm,n is Hamilton-laceable iff 6 < m, 6 < n, and one of m, n is even. Proof. The forward direction follows from Theorem 2.1. For the other direction, assume m < n. Case 1. m is odd and m < 13. In this case n is even. If n < 10, we have the conclusion by computation (Theorem 2.4), so assume n > 12. Then n splits into the even numbers 6 and n - 6, and the conclusion follows from the decomposition lemma by induction and Theorem 2.4. Case 2. m is even and m < 12. If n < 13, we have the conclusion by Theorem 2, so assume n > 14. Then n splits into 6 and n - 6; because (n - 6) - 6 > 2, the decomposition lemma and induction yield the result. Case 3. m is odd and m > 15. In this case n is even. Use induction on m; the cases 7 x n, 9 x n, 11 x n, and 13 x n follow from Case 1. For m > 15, an m x n board splits into 6 x n and (m - 6) x n boards. The first is HL by case 2 and the second is HL by the inductive hypothesis. Because (m - 6) - 6 > 2, the decomposition lemma applies. Case 4. m is even and m > 14. An m x n board splits into 6 x n and (m - 6) x n boards; because (m - 6) - 6 > 2, the result follows inductively from case 2 (for the base case) and the decomposition lemma. □ A dynamic demonstration at [15] shows all 322 paths in the case of the traditional 8 x 8 board; Figure 4 shows a typical case. As noted, this classic chessboard case was resolved in [1]; the work here settles all rectangular boards. 3 Traceable knights A graph is traceable if it has a Hamiltonian path. Cull and De Curtins [6] proved that Nm n is traceable if m > 5. Mark Krusemeyer reports having solved the complete problem in 120 Ars Math. Contemp. 9 (2015) 115-124 Figure 4: A snapshot (start at lower left, finish in center of second row) of a demonstration [15] that shows all 1024 knight's paths on a chessboard. Figure 5: A knight's path from (1,1) to (6, 2) on a 3 x 7 board. Similar paths exist with 7 replaced by 8 through 13, and hence for widths past 7. 1972 in an addendum to his doctoral thesis. We present here an approach to the m = 3 and m = 4 cases. For m = 3, N3j3 is disconnected, while the HP algorithm shows that N3,5 and N3,6 are not traceable and N3,n is traceable when n g {4, 7,8,9,10,11,12}. Moreover, for the last six cases, there is an HP that goes from the lower-left corner to the next-to-last rightmost point of the center row (Figure 5). Therefore it is a simple matter to chain two such paths together to get an HP in the case of n > 13. This settles the m = 3 case. The case of N4,n is harder. Using the HP algorithm with some edges deleted led to the gadget in Figure 6, which is the key to a proof that HPs exist for all N4,n Theorem 3.1 (Krusemeyer, Cull, De Curtins). The only connected knight graphs that are not traceable are N3,5, N3,6, N4,4. Proof. Cull and De Curtins [6], using methods similar to the methods of the present paper (decomposition and induction), showed that Nm,n is traceable when 5 < m < n. The case m = 3 was discussed above. A computer search shows that N4,4 is not traceable; this can also be proved by hand [16, p. 51]. Figure 6(b) shows N4,5, N4,6, and N4j7 with HPs from the lower left corner to the upper left corner. The gadget of Figure 6(a) can be used to extend any such path leftward to one with the same property, but on a board with three M. Dupuis and S. Wagon: Laceable knights 121 Figure 6: (a) The two disjoint paths in the 4 x 3 board allow one to construct Hamiltonian paths in any 4 x n board with n > 5. (b) Corner-to-corner paths for 4 x 5, 4 x 6, 4 x 7. more columns. This gives corner-to-corner HPs for all (4, n) with n > 5. The gadget was found by using the HP algorithm on a larger graph with various edges deleted so to force the condition of one edge out and one edge in. □ 4 Further applications of the algorithm The HP algorithm can be used on many families of bipartite graphs and works as well to study whether a nonbipartite graph is Hamilton-connected (HC), which means that there is a Hamiltonian path between any two vertices. Mathematical GraphData database has 572 graphs that are bipartite, Hamiltonian, vertex-transitive, and not a cycle; the largest has 2048 vertices. Using the HP algorithm we have shown that all 572 are HL. In particular, the HP algorithm shows that all the Foster graphs (connected, cubic, edge-transitive, and vertex-transitive) with 768 or fewer vertices (as well as the known Foster graphs up to 1000 vertices) are HL when bipartite and HC otherwise. Recall the folklore conjecture (based on a question by Lovasz about traceabiliy of vertex-transitive graphs; see [10]) that connected vertex-transitive graphs are Hamiltonian except for five small examples. Computations show that one almost always gets stronger Hamiltonian properties than just the existence of a Hamiltonian cycle. Question 4.1. Are even cycles the only bipartite, Hamiltonian, vertex-transitive graphs that are not Hamilton-laceable? And the same behavior has been observed for edge-transitive graphs. Question 4.2. Are even cycles the only bipartite, Hamiltonian, edge-transitive graphs that are not Hamilton-laceable? 122 Ars Math. Contemp. 9 (2015) 115-124 One can ask similar question for Hamilton-connected graphs. Of the 1557 nonbipartite, vertex-transitive, Hamiltonian graphs in the database (cycles excluded), the HP algorithm resolved the Hamilton-connected status of all of them. Only one — the dodecahedral graph — failed to be Hamilton-connected. Several of these graphs had over 1000 vertices; the largest was Kneser14,6 with 3003 vertices. Question 4.3. Are the odd cycles and the dodecahedral graph the only nonbipartite, Hamiltonian, vertex-transitive graphs that are not Hamilton-connected? And we have the same question with edge-transitivity replacing vertex-transitivity. Here are more detailed summaries for some interesting families: Generalized Petersen graphs GP(n, k). These cubic graphs, generalizations of the Petersen graph, are defined when n > 3 and k < n/2. They are all Hamiltonian except GP(6q + 5,2) and isomorphs (Alspach [1]). These are bipartite when n is even and k is odd. It is easy to see that GP(n, 1) is HL when bipartite, HC otherwise. Alspach and Liu [2] have shown that GP(2m, 3) is HL; some authors include cases such as GP(5, 3), which is isomorphic to the non-Hamiltonian Petersen graph GP(5, 2), but here we restrict to k < n/2. A recent paper [12] by Richter contains further results on Hamiltonian paths in this family. The HP algorithm shows that GP(n, k) is HL when n < 100 and so it is reasonable to conjecture that all bipartite graphs in the family are HL. Alspach and Qin [3] proved that GP(4m, 2m - 1) is HL. The situation regarding HC and HL for k < 3 is: GP(n, 1) is HL when n is even, HC otherwise (Alspach and Liu [2]). GP(n, 2) is HC iff n = 1 or 3(mod 6) [2, 12] GP(n, 3) is HL when n is even, HC otherwise [2]. Pensaert [11] found that GP(6,2) and GP(12,4) are not HC and conjectured that GP(n, k) is HC or HL whenever n > 3k +1. The case GP(3k + 1, k) is isomorphic to GP(3k + 1,3), a settled case. The HP algorithm extends the Pensaert examples by showing that GP(6q, 2q) is not HC when q < 12. The algorithm also shows that, with the exceptions mentioned for bipartite, non-Hamiltonian (GP(6q + 5,2)), and GP(6q, 2q), the graphs GP(n, k) are HC for k < 16 and 2k +1 < n < 100. So we have the conjectures that these last two results, positive and negative, hold in all cases. The I-graph computations discussed next show that GP(n, k) is HL in all the bipartite cases with n < 100. I-graphs I(n,j,k). These cubic graphs, where 1 < j, k < n and j, k = n/2, are generalizations of the GP family; GP(n, k) = I(n, 1, k) when k < n/2. An I-graph is bipartite and connected iff n is even, j and k are odd, and gcd(n, j, k) = 1. Horvat et al [7] give a simple condition for two I-graphs to be isomorphic. Computation suggests that all connected I-graphs, except the generalized Petersen exceptions, are Hamiltonian; that has been recently proved by Bonvicini and Pisanski [4]. Even stronger Hamiltonian properties appear to hold: the HP algorithm can be used to check for laceability: all bipartite, connected I(n, j, k) for n < 100 are HL. Bipartite Kneser graphs Hn,k. It is a well-known conjecture that the connected ones (k = n/2) are Hamiltonian; this has been proved for n < 27 [14]. These graphs are M. Dupuis and S. Wagon: Laceable knights 123 vertex- and edge-transitive, so it suffices to restrict the start point for a Hamiltonian path to a single vertex, v. Further, using permutations on the underlying n-set shows that one need only consider k + 1 types of pairs (v, F), the type being the size of the intersection of the set represented by v with that represented by F. These considerations speed up the HP algorithm, and the results are that Hn k is HL for all 4 < n < 14 and k < n/2, and also for (n, 2) with n < 43 and (n, 3) with n < 25. Note that ff3j1 is a 6-cycle and so is not HL. 5 Conclusion The work presented here shows how one can call on fast algorithms even for NP-complete problems as a way of learning about families of graphs, so long as the graphs are not terribly large. There are 853 bipartite Hamiltonian graphs in Mathematica's database and the algorithms presented here have resolved the laceability of all of them. Since finding Hamiltonian cycles or paths is NP-complete, it is not surprising that our methods fail for some large graphs. An idea that has proved useful on the larger examples (such as Kneser13,6, Kneser14,5, Kneser14,6, and an alternating group Cayley graph with 2520 vertices) is to use the cutting-edge technology of traveling salesman problem software, such as Concorde or LKH. One can turn a graph into a weighted complete graph with weights 0 on the edges and 1 on the nonedges; then if a shortest traveling salesman tour has weight 0, one has a Hamltonian cycle; if not, then no such cycle exists. This idea was used to determine Hamilton-connectivity in the large examples. Acknowledgments We are grateful to Brian Alspach and Bruce Richter for valuable comments, to Rasmus Kamper for helping with the setup of Concorde and LKH, and to referees for several helpful comments. References [1] B. Alspach, The classification of Hamiltonian generalized Petersen graphs, Journal of Combinatorial Theory Series B 34 (1983), 293-312. [2] B. Alspach and J. Liu, On the Hamilton connectivity of generalized Petersen graphs, Discrete Mathematics 309 (2009), 5461-5473. [3] B. Alspach and Y. Qin, Hamilton-connected Cayley graphs on Hamiltonian groups, Europ. J. Combinatorics 22 (2001), 777-787. [4] S. Bonvicini and T. Pisanski, Classification of Hamiltonian I-graphs and good walks in certain graph bundles, preprint 2012. [5] A. Conrad, T. Hindrichs, H. Morsy, and I. Wegener, Solution of the knight's Hamiltonian path problem on chessboards, Discrete Applied Mathematics 50 (1994), 125-134. [6] P. Cull and J. De Curtins, Knight's tour revisited, Fibonacci Quarterly 16 (1978), 276-285. [7] J. P. Hutchinson and S. Wagon, Kempe revisited, American Mathematical Monthly 105 (1998), 170-174. [8] R. Gaebler and T.-W. Yang, Knight's tours, unpublished notes 1999, http://gaebler. us/share/Knight_tour.html. [9] B. Horvat, T. Pisanski, and A. Zitnik, Isomorphism checking of I-graphs, Graphs and Combinatorics 28 (2012), 823-830. 124 Ars Math. Contemp. 9 (2015) 115-124 [10] K. Klavdija and D. Marusic, Hamilton cycles and paths in vertex-transitive graphs — current directions, Discrete Mathematics 309 (2009), 5491-5500. [11] W. P.J. Pensaert, Hamilton paths in generalized Petersen graphs, Masters Thesis, Univ. of Waterloo, (2002), http://etd.uwaterloo.ca/etd/wpjpensaert2 0 02.pdf. [12] B. Richter, Hamilton paths in generalized Petersen graphs, preprint, June 2012. [13] A. Schwenk, Which rectangular chessboards have a knight's tour?, Mathematics Magazine 64 (1991), 325-332. [14] I. Shields and C. D. Savage, A note on Hamilton cycles in Kneser graphs, Bulletin of the Institute Combinatorics and its Applications 40 (2004), 13-22. [15] S. Wagon, Laceable knight graphs, Wolfram Demonstrations Project (2012) http://demonstrations.wolfram.com/LaceableKnightGraphs [16] J. Watkins, Across the Board: The Mathematics of Chessboard Problems, Princeton Univ. Press, Princeton, New Jersey, 2004.