Gráfica de la torre

En teoría de grafos , el grafo de una torre es un grafo no dirigido que representa todos los movimientos legales de la pieza de ajedrez de torre en un tablero de ajedrez . Cada vértice del grafo de una torre representa un cuadrado en un tablero de ajedrez, y hay un borde entre dos cuadrados cualesquiera que compartan una fila (fila) o columna (columna), los cuadrados entre los que una torre puede moverse. Estos grafos se pueden construir para tableros de ajedrez de cualquier forma rectangular. Aunque los grafos de torre tienen solo una importancia menor en la tradición del ajedrez, son más importantes en las matemáticas abstractas de los grafos a través de sus construcciones alternativas: los grafos de torre son el producto cartesiano de dos grafos completos , y son los grafos lineales de grafos bipartitos completos . Los grafos de torre cuadrados constituyen los grafos de Hamming bidimensionales .

Los grafos de torre son altamente simétricos, ya que tienen simetrías que llevan cada vértice a cada otro vértice. En los grafos de torre definidos a partir de tableros de ajedrez cuadrados, de manera más fuerte, cada dos aristas son simétricas, y cada par de vértices es simétrico a cada otro par a la misma distancia en movimientos (lo que hace que el grafo sea transitivo en la distancia ). Para tableros de ajedrez rectangulares cuyo ancho y alto son primos entre sí , los grafos de torre son grafos circulantes . Con una excepción, los grafos de torre se pueden distinguir de todos los demás grafos usando solo dos propiedades: el número de triángulos a los que pertenece cada arista y la existencia de un ciclo único de $4$ que conecta cada par de vértices no adyacentes.

Los grafos de torre son grafos perfectos . En otras palabras, cada subconjunto de casillas del tablero de ajedrez se puede colorear de modo que no haya dos casillas en una fila o columna que tengan el mismo color, utilizando una cantidad de colores igual a la cantidad máxima de casillas del subconjunto en cualquier fila o columna individual (el número de camarilla del subgrafo inducido ). Esta clase de subgrafos inducidos son un componente clave de una descomposición de grafos perfectos utilizada para demostrar el teorema del grafo perfecto fuerte , que caracteriza a todos los grafos perfectos. El número de independencia y el número de dominación del grafo de una torre son iguales al menor de los valores de ancho y alto del tablero de ajedrez. En términos de ajedrez, el número de independencia es la cantidad máxima de torres que se pueden colocar sin atacarse entre sí; el número de dominación es la cantidad mínima necesaria para atacar todas las casillas desocupadas del tablero. Los grafos de torre son grafos bien cubiertos , lo que significa que la colocación de torres que no atacan una a la vez nunca puede atascarse hasta que se alcance un conjunto de tamaño máximo.

Definición y construcciones matemáticas

El gráfico de una torre $de n \times m representa los movimientos de una torre en un tablero de ajedrez$ $de n \times m$ . ^[1] Sus vértices representan los cuadrados del tablero de ajedrez y pueden tener coordenadas $(x, y)$ , donde $1 \leq x \leq n$ y $1 \leq y \leq m$ . Dos vértices con coordenadas $(x 1, y 1)$ y $(x 2, y 2)$ son adyacentes si y solo si $x 1 = x 2$ o $y 1 = y 2$ . (Si $x 1 = x 2$ , los vértices comparten una fila y están conectados por un movimiento de torre vertical; si $y 1 = y 2$ , comparten una fila y están conectados por un movimiento de torre horizontal.) ^[1]

Los cuadrados de una misma fila o columna están todos conectados directamente entre sí, por lo que cada fila y columna forman una camarilla , un subconjunto de vértices que forman un grafo completo . El grafo de torre completo para un tablero de ajedrez $de n \times m$ se puede formar a partir de estos dos tipos de camarillas, como el producto cartesiano de grafos $K n ◻ K m$ . ^[2] Debido a que el grafo de torre para un tablero de ajedrez cuadrado es el producto cartesiano de camarillas de igual tamaño, es un ejemplo de grafo de Hamming . Su dimensión como grafo de Hamming es dos, y cada grafo de Hamming bidimensional es un grafo de torre para un tablero de ajedrez cuadrado. ^[3] Los grafos de torre cuadrados también se denominan " grafos de cuadrados latinos "; aplicados a un cuadrado latino, sus aristas describen pares de cuadrados que no pueden contener el mismo valor. ^[4] Los grafos de Sudoku son grafos de torre con algunas aristas adicionales, que conectan cuadrados de un Sudoku que deberían tener valores desiguales. ^[5]

Geométricamente, los grafos de torre pueden formarse mediante conjuntos de vértices y aristas (los esqueletos ) de una familia de politopos convexos , los productos cartesianos de pares de politopos vecinos . ^[6] Por ejemplo, el duoprisma 3-3 es una forma de cuatro dimensiones formada como el producto cartesiano de dos triángulos , y tiene un grafo de torre $de 3 \times 3$ como esqueleto. ^[7]

Regularidad y simetría

Fuerte regularidad

Moon (1963) y Hoffman (1964) observan que el gráfico de la torre (o equivalentemente, como lo describen, el gráfico lineal del gráfico bipartito completo ) tiene todas las siguientes propiedades: $m\veces n$ $Estilo de visualización K_{m,n}$

Tiene vértices, uno por cada casilla del tablero. Cada vértice es adyacente a las aristas, lo que lo conecta con las casillas de la misma fila y las casillas de la misma columna. ${\estilo de visualización mn}$ $m\veces n$ ${\estilo de visualización m+n-2}$ ${\estilo de visualización m-1}$ ${\estilo de visualización n-1}$
Los triángulos dentro del grafo de la torre están formados por triples de cuadrados dentro de una misma fila o columna. Cuando , exactamente las aristas (las que conectan cuadrados de la misma fila) pertenecen a triángulos; las aristas restantes (las que conectan cuadrados de la misma columna) pertenecen a triángulos. Cuando , cada arista pertenece a triángulos. $m\neq n$ $n{\tbinom {m}{2}}$ ${\estilo de visualización m-2}$ $m{\tbinom {n}{2}}$ ${\estilo de visualización n-2}$ $m=n$ $m-2=n-2$
Cada dos vértices no adyacentes pertenecen a un único ciclo de vértices , es decir, el único rectángulo que utiliza los dos vértices como esquinas. ${\estilo de visualización 4}$

Demuestran que, excepto en el caso , estas propiedades caracterizan de forma única al grafo de la torre. Es decir, los grafos de la torre son los únicos grafos con estas cantidades de vértices, aristas, triángulos por arista y con un ciclo único de 4 a través de cada dos vértices no adyacentes. ^[8]^[9] $m=n=4$

Cuando , estas condiciones pueden abreviarse indicando que un grafo de torre es un grafo fuertemente regular con parámetros . Estos parámetros describen la cantidad de vértices, la cantidad de aristas por vértice, la cantidad de triángulos por arista y la cantidad de vecinos compartidos para dos vértices no adyacentes, respectivamente. ^[1] Por el contrario, todo grafo fuertemente regular con estos parámetros debe ser un grafo de torre, a menos que . ^[8]^[9] $m=n$ $n\veces n$ $\operatorname {srg} (n^{2},2n-2,n-2,2)$ $n\veces n$ ${\estilo de visualización n=4}$

Cuando , hay otro grafo fuertemente regular, el grafo de Shrikhande , con los mismos parámetros que el grafo de la torre. ^[10] El grafo de Shrikhande obedece a las mismas propiedades enumeradas por Moon y Moser. Se puede distinguir del grafo de la torre en que la vecindad de cada vértice en el grafo de Shrikhande está conectada para formar un -ciclo . En contraste, en el grafo de la torre, la vecindad de cada vértice forma dos triángulos, uno para su fila y otro para su columna, sin ninguna arista de una parte de la vecindad a la otra. ^[11] Otra forma de distinguir el grafo de la torre del grafo de Shrikhande utiliza números de cobertura de camarillas : el grafo de la torre puede estar cubierto por cuatro camarillas (las cuatro filas o las cuatro columnas del tablero de ajedrez) mientras que se necesitan seis camarillas para cubrir el grafo de Shrikhande. ^[10] ${\estilo de visualización n=4}$ $4\times 4$ $4\times 4$ ${\estilo de visualización 6}$ $4\times 4$ $4\times 4$ ${\estilo de visualización n=4}$

Simetría

Los grafos de la torre son transitivos de vértice , lo que significa que tienen simetrías que llevan cada vértice a cada otro vértice. Esto implica que cada vértice tiene un número igual de aristas: son - regulares . Los grafos de la torre son los únicos grafos regulares formados a partir de los movimientos de piezas de ajedrez estándar de esta manera. ^[12] Cuando , las simetrías del grafo de la torre se forman permutando independientemente las filas y columnas del grafo, por lo que el grupo de automorfismos del grafo tiene elementos. Cuando , el grafo tiene simetrías adicionales que intercambian las filas y columnas, por lo que el número de automorfismos es . ^[13] ${\estilo de visualización (m+n-2)}$ $m\neq n$ $m!n!$ $m=n$ ${\estilo de visualización 2n!^{2}}$

Dos vértices cualesquiera en el grafo de una torre están a una o dos distancias entre sí, según sean adyacentes o no, respectivamente. Dos vértices no adyacentes cualesquiera pueden transformarse en otros dos vértices no adyacentes cualesquiera mediante una simetría del grafo. Cuando el grafo de la torre no es cuadrado, los pares de vértices adyacentes caen en dos órbitas del grupo de simetría según sean adyacentes horizontal o verticalmente, pero cuando el grafo es cuadrado cualesquiera dos vértices adyacentes también pueden mapearse entre sí mediante una simetría y, por lo tanto, el grafo es transitivo en cuanto a la distancia . ^[14]

Cuando y son primos entre sí , el grupo de simetría del grafo de la torre contiene como subgrupo al grupo cíclico que actúa permutando cíclicamente los vértices. Por lo tanto, en este caso, el grafo de la torre es un grafo circulante . ^[15] ${\estilo de visualización m}$ ${\estilo de visualización n}$ $S_{m}\times S_{n}$ $C_{mn}=C_{m}\times C_{n}$ ${\estilo de visualización mn}$

Los grafos de la torre cuadrada son conexos-homogéneos , lo que significa que cada isomorfismo entre dos subgrafos inducidos conexos puede extenderse a un automorfismo de todo el grafo. ^[16]

Otras propiedades

Perfección

El grafo de la torre 3×3 (el grafo del duoprisma 3-3 ), coloreado con tres colores y mostrando una camarilla de tres vértices. En este grafo y en cada uno de sus subgrafos inducidos el número cromático es igual al número de camarilla, por lo que es un grafo perfecto.

El grafo de una torre también puede verse como el grafo lineal de un grafo bipartito completo $K n, m$ — es decir, tiene un vértice para cada arista de $K n, m$ , y dos vértices del grafo de la torre son adyacentes si y solo si las aristas correspondientes del grafo bipartito completo comparten un punto final común. ^[2]^[17] En esta visión, una arista en el grafo bipartito completo desde el $i$ ésimo vértice en un lado de la bipartición hasta el $j$ ésimo vértice en el otro lado corresponde a un cuadrado de tablero de ajedrez con coordenadas $(i, j)$ . ^[1]

Cualquier grafo bipartito es un subgrafo de un grafo bipartito completo, y correspondientemente cualquier grafo lineal de un grafo bipartito es un subgrafo inducido de un grafo de torre. ^[18] Los grafos lineales de grafos bipartitos son perfectos : en ellos, y en cualquiera de sus subgrafos inducidos, el número de colores necesarios en cualquier coloración de vértice es el mismo que el número de vértices en el subgrafo completo más grande . Los grafos lineales de grafos bipartitos forman una familia importante de grafos perfectos: son una de las pocas familias utilizadas por Chudnovsky et al. (2006) para caracterizar los grafos perfectos y mostrar que todo grafo sin agujero impar y sin antiagujero impar es perfecto. ^[19] En particular, los grafos de torre son en sí mismos perfectos.

Como el gráfico de una torre es perfecto, el número de colores necesarios en cualquier coloración del gráfico es simplemente el tamaño de su grupo más grande. Los grupos de un gráfico de una torre son los subconjuntos de una sola fila o una sola columna, y el más grande de estos tiene un tamaño $máx(m, n)$ , por lo que este es también el número cromático del gráfico. Una coloración $n de un gráfico de torre$ $n \times n$ puede interpretarse como un cuadrado latino : describe una forma de llenar las filas y columnas de una cuadrícula $n \times n$ $con n$ valores diferentes de tal manera que el mismo valor no aparezca dos veces en ninguna fila o columna. ^[20] De la misma manera, una coloración de un gráfico de torre rectangular corresponde a un rectángulo latino . ^[21] Aunque encontrar una coloración óptima del grafo de una torre es sencillo, es NP-completo determinar si una coloración parcial puede extenderse a una coloración del grafo completo (este problema se llama extensión de precoloración ). De manera equivalente, es NP-completo determinar si un cuadrado latino parcial puede completarse a un cuadrado latino completo. ^[22]

Independencia

Una colocación no atacante de ocho torres en un tablero de ajedrez, formando un conjunto independiente máximo en el gráfico de la torre correspondiente.

Un conjunto independiente en un grafo de torre es un conjunto de vértices, de los cuales ninguno pertenece a la misma fila o columna del grafo; en términos de ajedrez, corresponde a una colocación de torres de las cuales ninguno se ataca entre sí. Los grafos perfectos también pueden describirse como los grafos en los que, en cada subgrafo inducido, el tamaño del conjunto independiente más grande es igual al número de camarillas en una partición de los vértices del grafo en un número mínimo de camarillas. En un grafo de torre, los conjuntos de filas o los conjuntos de columnas (el que tenga menos conjuntos) forman dicha partición óptima. El tamaño del conjunto independiente más grande en el grafo es, por lo tanto, $min(m, n)$ . ^[1]

Los gráficos de torre son gráficos bien cubiertos : cada conjunto independiente en un gráfico de torre se puede extender a un conjunto independiente máximo, y cada conjunto independiente máximo en un gráfico de torre tiene el mismo tamaño, $min(m, n)$ . ^[23]

Dominación

El número de dominación de un grafo es la cardinalidad mínima entre todos los conjuntos dominantes. En el grafo de la torre, un conjunto de vértices es un conjunto dominante si y solo si sus casillas correspondientes ocupan, o están a un movimiento de la torre de, todas las casillas en el tablero $m \times n$ . Para el tablero $m \times n,$ el número de dominación es $min(m, n)$ . ^[24]

En el grafo de la torre, un conjunto $k$ -dominante es un conjunto de vértices cuyos cuadrados correspondientes atacan a todos los demás cuadrados (a través del movimiento de una torre) al menos $k$ veces. Un conjunto $k$ -tupla dominante en el grafo de la torre es un conjunto de vértices cuyos cuadrados correspondientes atacan a todos los demás cuadrados al menos $k$ veces y son atacados a su vez al menos $k - 1$ veces. La cardinalidad mínima entre todos los conjuntos $k$ -dominantes y $k$ -tuplas dominantes son el número $de k -dominación y el número de$ $k$ -tupla dominación, respectivamente. En el tablero cuadrado, y para un número par $k$ , el número $de k$ -dominación es $nk /2$ cuando $n \geq (k 2 - 2 k)/4$ y $k < 2 n$ . De manera similar, el número de $k$ -tupla dominación es $n (k + 1)/2$ cuando $k$ es impar y menor que $2 n$ . ^[25]

Hamiltonicidad

El gráfico de cada torre contiene un ciclo hamiltoniano . ^[26] Sin embargo, estos ciclos pueden implicar movimientos entre casillas que están muy separadas dentro de una sola fila o columna del tablero de ajedrez. En cambio, el estudio de los "recorridos de la torre", en las matemáticas del ajedrez, se ha concentrado generalmente en un caso especial de estos ciclos hamiltonianos donde la torre está restringida a moverse solo a casillas adyacentes. Estos recorridos de torre de un solo paso solo existen en tableros con un número par de casillas. Desempeñan un papel central en la prueba del teorema de Gomory de que, si se eliminan dos casillas de colores opuestos de un tablero de ajedrez estándar, las casillas restantes siempre pueden cubrirse con fichas de dominó. ^[27] Se presentan junto con los recorridos del caballo en la primera obra que analiza los recorridos de las piezas de ajedrez, el Kavyalankara sánscrito del siglo IX de Rudrata . ^[28]

Espectro

El espectro del grafo de una torre (los valores propios de su matriz de adyacencia ) consta de los cuatro valores propios , , y . Debido a que todos ellos son números enteros, los grafos de torre son grafos integrales . Solo hay tres clases de grafos (y un número finito de grafos excepcionales) que pueden tener cuatro valores propios, siendo uno de los cuatro ; una de las tres clases es la clase de los grafos de torre. Para la mayoría de las combinaciones de y , el grafo de torre es espectralmente único: ningún otro grafo tiene el mismo espectro. En particular, esto es cierto cuando o , o cuando los dos números y suman al menos 18 y no tienen la forma . ^[29] ${\estilo de visualización m+n-2}$ ${\estilo de visualización m-2}$ ${\estilo de visualización n-2}$ ${\estilo de visualización -2}$ ${\estilo de visualización -2}$ ${\estilo de visualización m}$ ${\estilo de visualización n}$ $m\veces n$ ${\estilo de visualización n=2}$ ${\estilo de visualización n=m-1}$ ${\estilo de visualización m}$ ${\estilo de visualización n}$ $2t^{2}\pm t$

En otros gráficos

Los grafos para los cuales los vecinos de cada vértice inducen un grafo de torre han sido llamados localmente cuadrícula . Algunos ejemplos incluyen los grafos de Johnson , para los cuales los vecinos de cada vértice forman un grafo de torre. Se conocen otros ejemplos, y para algunos grafos de torre, se conoce una clasificación completa. Por ejemplo, hay dos grafos cuyos vecindarios son todos grafos de torre: son el grafo de Johnson y el grafo complementario de un grafo de torre. ^[30] $J(n,k)$ $k\veces (nk)$ $3\times 3$ $J(6,3)$ $4\times 4$

Véase también

Gráfica del obispo
Complejo del tablero de ajedrez , complejo de independencia del grafo de la torre
Gráfica del rey
Gráfica del caballero
Gráfico reticular , gráfico de adyacencias horizontales y verticales de cuadrados en un tablero de ajedrez.
Gráfica de la reina

Referencias

^ abcde Laskar, Renu ; Wallis, Charles (1999), "Gráficos de tablero de ajedrez, diseños relacionados y parámetros de dominación", Journal of Statistical Planning and Inference , 76 (1–2): 285–294, doi :10.1016/S0378-3758(98)00132-3, MR 1673351.
^ ab Stones, Douglas S. (2010), "Las múltiples fórmulas para el número de rectángulos latinos", Electronic Journal of Combinatorics , 17 (1): Artículo 1, 46, doi : 10.37236/487 , MR 2661404
^ Azizoğlu, M. Cemil; Eğecioğlu, Ömer (2003), "Conjuntos extremos que minimizan el límite normalizado por dimensión en gráficos de Hamming", SIAM Journal on Discrete Mathematics , 17 (2): 219–236, doi :10.1137/S0895480100375053, MR 2032290.
^ Goethals, J.-M.; Seidel, JJ (1970), "Gráficos fuertemente regulares derivados de diseños combinatorios", Revista canadiense de matemáticas , 22 (3): 597–614, doi : 10.4153/CJM-1970-067-9 , MR 0282872, S2CID 199082328.
^ Herzberg, Agnes M. ; Murty, M. Ram (2007), "Cuadrados de sudoku y polinomios cromáticos" (PDF) , Avisos de la American Mathematical Society , 54 (6): 708–717, MR 2327972
^ Matschke, Benjamin; Pfeifle, Julian; Pilaud, Vincent (2011), "Polítopos prodsimpliciales-vecinos", Geometría discreta y computacional , 46 (1): 100–131, arXiv : 0908.4177 , doi :10.1007/s00454-010-9311-y, MR 2794360, S2CID 2070310
^ Moore, Doug (1992), "Entendiendo los simploides", en Kirk, David (ed.), Graphics Gems III , Academic Press , págs. 250-255, doi :10.1016/b978-0-08-050755-2.50057-9
^ ab Moon, JW (1963), "Sobre el gráfico lineal del bígrafo completo", Annals of Mathematical Statistics , 34 (2): 664–667, doi : 10.1214/aoms/1177704179.
^ ab Hoffman, AJ (1964), "Sobre el gráfico lineal del gráfico bipartito completo", Annals of Mathematical Statistics , 35 (2): 883–885, doi : 10.1214/aoms/1177703593 , MR 0161328.
^ ab Fiala, Nick C.; Haemers, Willem H. (2006), "Gráficos fuertemente regulares 5-cromáticos", Discrete Mathematics , 306 (23): 3083–3096, doi : 10.1016/j.disc.2004.03.023 , MR 2273138.
^ Burichenko, vicepresidente; Makhnev, AA (2011), "Об автоморфизмах сильно регулярных локально циклических графов" [Sobre los automorfismos de gráficos localmente cíclicos fuertemente regulares], Doklady Akademii Nauk (en ruso), 441 (2): Señor 2953786Traducido en Doklady Mathematics 84 (3): 778–782, 2011, doi :10.1134/S1064562411070076. De la primera página de la traducción: "El gráfico de Shrikhande es el único gráfico localmente hexagonal fuertemente regular con parámetros (16, 6, 2, 2)".
^ Elkies, Noam (otoño de 2004), "Glosario de teoría de grafos", Freshman Seminar 23j: Chess and Mathematics , Departamento de Matemáticas de la Universidad de Harvard , consultado el 3 de mayo de 2023.
^ Harary, Frank (1958), "Sobre el número de gráficos bicolores", Pacific Journal of Mathematics , 8 (4): 743–755, doi : 10.2140/pjm.1958.8.743 , MR 0103834. Véase en particular la ecuación (10), pág. 748 para el grupo de automorfismos del grafo de la torre, y la discusión anterior sobre la ecuación para el orden de este grupo. $n\veces n$
^ Biggs, Norman (1974), "La simetría de los gráficos de líneas", Utilitas Mathematica , 5 : 113–121, MR 0347684.
^ Esto se desprende de la definición del grafo de la torre como un grafo de producto cartesiano, junto con la Proposición 4 de Broere, Izak; Hattingh, Johannes H. (1990), "Productos de grafos circulantes", Quaestiones Mathematicae , 13 (2): 191–216, doi :10.1080/16073606.1990.9631612, MR 1068710.
^ Gray, R.; Macpherson, D. (2010), "Grafos homogéneos conectados contables", Journal of Combinatorial Theory , Serie B, 100 (2): 97–118, doi : 10.1016/j.jctb.2009.04.002 , MR 2595694. Véase en particular el Teorema 1, que identifica estos gráficos como gráficos lineales de gráficos bipartitos completos.
^ Para la equivalencia entre productos cartesianos de grafos completos y grafos lineales de grafos bipartitos completos, véase de Werra, D.; Hertz, A. (1999), "On perfectness of sums of graphs" (PDF) , Discrete Mathematics , 195 (1–3): 93–101, doi : 10.1016/S0012-365X(98)00168-X , MR 1663807.
^ de Werra y Hertz (1999).
^ Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del grafo perfecto fuerte" (PDF) , Anales de Matemáticas , 164 (1): 51–229, arXiv : math/0212070 , doi :10.4007/annals.2006.164.51, JSTOR 20159988, S2CID 119151552.
^ Para la equivalencia entre la coloración de los bordes de grafos bipartitos completos y cuadrados latinos, véase, por ejemplo, LeSaulnier, Timothy D.; Stocker, Christopher; Wenger, Paul S.; West, Douglas B. (2010), "Rainbow matching in edge-colored graphs", Electronic Journal of Combinatorics , 17 (1): Nota 26, 5, doi : 10.37236/475 , MR 2651735.
^ Stones, Douglas S. (2010), "Las múltiples fórmulas para el número de rectángulos latinos", Electronic Journal of Combinatorics , 17 (1): A1:1–A1:46, doi : 10.37236/487 , MR 2661404
^ Colbourn, Charles J. (1984), "La complejidad de completar cuadrados latinos parciales", Discrete Applied Mathematics , 8 (1): 25–30, doi : 10.1016/0166-218X(84)90075-1 , MR 0739595.
^ Para una declaración equivalente a la propiedad bien cubierta de los grafos de Rook, en términos de emparejamientos en grafos bipartitos completos, véase Lesk, M.; Plummer, MD; Pulleyblank, WR (1984), "Equi-matchable graphs", en Bollobás, Béla (ed.), Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference, in Honour of Paul Erdős , Londres: Academic Press, pp. 239–254, MR 0777180.
^ Yaglom, AM ; Yaglom, IM (1987), "Solución al problema 34b", Problemas matemáticos desafiantes con soluciones elementales, Dover, pág. 77, ISBN 9780486318578.
^ Burchett, Paul; Lane, David; Lachniet, Jason (2009), " Dominación $k y dominación$ $k$ -tupla en el gráfico de la torre y otros resultados", Congressus Numerantium , 199 , 187-204.
^ Hurley, CB; Oldford, RW (febrero de 2011), "Gráficos como infraestructura de navegación para espacios de datos de alta dimensión", Computational Statistics , 26 (4): 585–612, doi :10.1007/s00180-011-0228-6, S2CID 54220980
^ Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems , Princeton University Press, pág. 12, ISBN 9780691130620
^ Murray, HJR (enero de 1902), "El recorrido del caballo: antiguo y oriental", The British Chess Magazine , vol. 22, núm. 1, págs. 1–7
^ Doob, Michael (1970), "Sobre la caracterización de ciertos gráficos con cuatro valores propios por sus espectros", Álgebra lineal y sus aplicaciones , 3 (4): 461–482, doi : 10.1016/0024-3795(70)90037-6 , MR 0285432
^ Cohen, Arjeh M. (1990), "Reconocimiento local de gráficos, edificios y geometrías relacionadas" (PDF) , en Kantor, William M.; Liebler, Robert A.; Payne, Stanley E.; Shult, Ernest E. (eds.), Geometrías finitas, edificios y temas relacionados: artículos de la Conferencia sobre edificios y geometrías relacionadas celebrada en Pingree Park, Colorado, del 17 al 23 de julio de 1988 , Oxford Science Publications, Oxford University Press, págs. 85-94, MR 1072157; véanse en particular las páginas 89-90

Enlaces externos

Weisstein, Eric W. , "Gráfico de torre", MathWorld