Premium
Connectivity of Knight's Graphs
Author(s) -
Rhodes F.,
Wilson S.
Publication year - 1993
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/s3-67.2.225
Subject(s) - knight , citation , library science , mathematics , combinatorics , history , computer science , physics , astronomy
This paper is concerned with connectivity of graphs associated with generalized knight's moves. The minimal connected generalized knight's graphs are shown to be planar or toroidal, which was unexpected in view of the complex nature of the graph generated by knight's moves on a chess-board. Each move of a knight in chess takes the knight two steps parallel to one side of the board and one step parallel to the other side. Using moves of this kind a knight can move between any two positions on a standard 8 by 8 chess-board. Indeed it can move between any two positions on a 3 by 4 board, but not on any smaller board. A metrical geometry on the digital plane determined by standard knight's moves has been studied recently (1,6), and further metrics associated with generalized knight's moves have been noted (2). The first step is to determine which knight's moves are transitive on an unbounded board. It is then natural to try to determine for each of these the smallest board on which it is transitive. It is convenient to express the problem in terms of knight's graphs in which the vertices are points in the plane with integer coefficients and the edges correspond to the knight's moves. An edge in the graph of a {p, ^}-knight joins two vertices where the difference between one of their coordinates is p and the difference between the other is q. Transitivity of a knight's moves on a board corresponds to connectivity of a knight's graph. The problem on the unrestricted set of vertices is easily solved. It is shown in §2 that the {p, ^}-knight's graph on Z2 is connected if and only if p and q are mutually prime and their sum is odd. This is a special case of more general results on knight's graphs on Z" which have been studied by G. A. Jones (3). The problem on restricted sets of vertices is more difficult. In this paper it is shown that if the {p, q)-knight's graph is connected on Z2 and p