gráfico de torre

Gráfico de movimientos de torre de ajedrez

En teoría de grafos , la gráfica de una torre es una gráfica no dirigida que representa todos los movimientos legales de la pieza de ajedrez de la torre en un tablero de ajedrez . Cada vértice del gráfico de una torre representa un cuadrado en un tablero de ajedrez, y hay un borde entre dos cuadrados cualesquiera que comparten una fila (rango) o columna (archivo), los cuadrados entre los que se puede mover una torre. Estos gráficos se pueden construir para tableros de ajedrez de cualquier forma rectangular. Aunque las gráficas de la torre tienen una importancia menor en la tradición del ajedrez, son más importantes en las matemáticas abstractas de las gráficas a través de sus construcciones alternativas: las gráficas de la torre son el producto cartesiano de dos gráficas completas y son las gráficas lineales de gráficas bipartitas completas . Las gráficas de la torre cuadrada constituyen las gráficas de Hamming bidimensionales .

Las gráficas de Rook son altamente simétricas y tienen simetrías que llevan cada vértice a cada otro vértice. En los gráficos de torre definidos a partir de tableros de ajedrez cuadrados, más fuertemente, cada dos aristas son simétricas y cada par de vértices es simétrico con respecto a todos los demás pares a la misma distancia en movimientos (lo que hace que el gráfico sea transitivo en distancia ). Para tableros de ajedrez rectangulares cuyo ancho y alto son relativamente primos , las gráficas de la torre son gráficas circulantes . Con una excepción, las gráficas de la torre se pueden distinguir de todas las demás gráficas 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.

Las gráficas de Rook son gráficas perfectas . En otras palabras, cada subconjunto de cuadrados del tablero de ajedrez se puede colorear de modo que no haya dos cuadrados en una fila o columna que tengan el mismo color, usando una cantidad de colores igual al número máximo de cuadrados del subconjunto en cualquier fila o columna (el número de camarilla del subgrafo inducido ). Esta clase de subgrafos inducidos es un componente clave de una descomposición de gráficos perfectos que se utiliza para demostrar el teorema del gráfico perfecto fuerte , que caracteriza a todos los gráficos perfectos. El número de independencia y el número de dominación del gráfico de una torre son iguales al menor entre el ancho y el alto del tablero de ajedrez. En términos de ajedrez, el número de independencia es el número máximo de torres que se pueden colocar sin atacarse entre sí; el número de dominación es el número mínimo necesario para atacar todas las casillas desocupadas del tablero. Los gráficos de la torre están bien cubiertos , lo que significa que colocar las torres no atacantes una a la vez nunca puede quedarse atascado hasta que se alcance un conjunto de tamaño máximo.

Definición y construcciones matemáticas.

La gráfica de una torre de n × m representa los movimientos de una torre en un tablero de ajedrez de n × m . ^[1] Sus vértices representan los cuadrados del tablero de ajedrez, y se les pueden dar coordenadas ( x , y ) , donde 1 ≤ x ≤ n y 1 ≤ y ≤ m . Dos vértices con coordenadas ( x ₁ , y ₁ ) y ( x ₂ , y ₂ ) son adyacentes si y sólo si x ₁ = x ₂ o y ₁ = y ₂ . (Si x ₁ = x ₂ , los vértices comparten una fila y están conectados mediante un movimiento de torre vertical; si ^y 1 ₌ y 2 _, comparten un rango y están conectados mediante un movimiento de torre horizontal).

Los cuadrados de una sola fila o fila están todos directamente conectados entre sí, por lo que cada fila y fila forma una camarilla , un subconjunto de vértices que forman un gráfico completo . La gráfica completa de la torre para un tablero de ajedrez de n × m se puede formar a partir de estos dos tipos de camarillas, como el producto cartesiano de las gráficas K _n ◻ K _m . ^[2] Debido a que la gráfica de la torre para un tablero de ajedrez cuadrado es el producto cartesiano de camarillas de igual tamaño, es un ejemplo de gráfica de Hamming . Su dimensión como gráfico de Hamming es dos, y cada gráfico de Hamming bidimensional es el gráfico de una torre para un tablero de ajedrez cuadrado. ^[3] Las gráficas de torre cuadrada también se denominan " gráficas cuadradas latinas "; aplicado a un cuadrado latino, sus aristas describen pares de cuadrados que no pueden contener el mismo valor. ^[4] Los gráficos de Sudoku son gráficos de torre con algunos bordes adicionales, que conectan cuadrados de un Sudoku que deberían tener valores desiguales. ^[5]

El duoprisma 3-3 , un politopo convexo de cuatro dimensiones que tiene un gráfico de torre de 3 × 3 como esqueleto

Geométricamente, los gráficos de la 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 una gráfica de torre de 3 × 3 como esqueleto. ^[7]

Regularidad y simetría

Fuerte regularidad

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

• Tiene vértices, uno por cada casilla del tablero de ajedrez. Cada vértice es adyacente a los bordes, conectándolo a los cuadrados del mismo rango y a los cuadrados del mismo archivo. ${\displaystyle mn}$ ${\displaystyle m\times n}$ ${\displaystyle m+n-2}$ ${\displaystyle m-1}$ ${\displaystyle n-1}$
• Los triángulos dentro del gráfico de la torre están formados por tripletas de cuadrados dentro de una sola fila o fila. Cuando , exactamente las aristas (las que conectan cuadrados del mismo rango) pertenecen a triángulos; los bordes restantes (los que conectan cuadrados en el mismo archivo) pertenecen a triángulos. Cuando , cada arista pertenece a triángulos. ${\displaystyle m\neq n}$ ${\displaystyle n{\tbinom {m}{2}}}$ ${\displaystyle m-2}$ ${\displaystyle m{\tbinom {n}{2}}}$ ${\displaystyle n-2}$ ${\displaystyle m=n}$ ${\displaystyle m-2=n-2}$
• Cada dos vértices no adyacentes pertenecen a un ciclo de vértices único , es decir, el único rectángulo que utiliza los dos vértices como esquinas. ${\displaystyle 4}$

Muestran que, excepto en el caso , estas propiedades caracterizan de forma única la gráfica de la torre. Es decir, las gráficas de la torre son las únicas gráficas con estos números 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]} ${\displaystyle m=n=4}$

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

El gráfico de Shrikhande incrustado en un toroide. Este no es un gráfico de torre, pero es fuertemente regular con los mismos parámetros que el gráfico de la torre. ${\displaystyle 4\times 4}$

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

Simetría

Los gráficos de Rook son transitivos por vértices , lo que significa que tienen simetrías que llevan cada vértice a cada otro vértice. Esto implica que cada vértice tiene el mismo número de aristas: son regulares . Las gráficas de la torre son las únicas gráficas regulares formadas de esta manera a partir de los movimientos de piezas de ajedrez estándar. ^[12] Cuando , las simetrías del gráfico de la torre se forman permutando independientemente las filas y columnas del gráfico, por lo que el grupo de automorfismos del gráfico tiene elementos. Cuando , el gráfico tiene simetrías adicionales que intercambian las filas y columnas, por lo que el número de automorfismos es . ^[13] ${\displaystyle (m+n-2)}$ ${\displaystyle m\neq n}$ ${\displaystyle m!n!}$ ${\displaystyle m=n}$ ${\displaystyle 2n!^{2}}$

Dos vértices cualesquiera en el gráfico de una torre están a una distancia de uno o dos entre sí, según sean adyacentes o no adyacentes, respectivamente. Dos vértices no adyacentes cualesquiera pueden transformarse en otros dos vértices no adyacentes cualesquiera mediante una simetría del gráfico. Cuando la gráfica de la torre no es cuadrada, los pares de vértices adyacentes caen en dos órbitas del grupo de simetría según sean adyacentes horizontal o verticalmente, pero cuando la gráfica es cuadrada, dos vértices adyacentes cualesquiera también pueden ser mapeados entre sí mediante un simetría y, por lo tanto, la gráfica es transitiva en distancia . ^[14]

Cuando y son primos relativos , el grupo de simetría de la gráfica de la torre contiene como subgrupo al grupo cíclico que actúa permutando cíclicamente los vértices. Por tanto, en este caso, la gráfica de la torre es una gráfica circulante . ^[15] ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle S_{m}\times S_{n}}$ ${\displaystyle C_{mn}=C_{m}\times C_{n}}$ ${\displaystyle mn}$

Los gráficos de torre cuadrada son conexos-homogéneos , lo que significa que cada isomorfismo entre dos subgrafos inducidos conectados se puede extender a un automorfismo de todo el gráfico. ^[dieciséis]

Otras propiedades

Perfección

La gráfica de la torre 3×3 (la gráfica del duoprisma 3-3 ), coloreada con tres colores y mostrando una camarilla de tres vértices. En este gráfico 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 gráfico perfecto.

La gráfica de una torre también se puede ver como la gráfica lineal de un gráfico bipartito completo K _{n , m} , es decir, tiene un vértice para cada arista de K _{n , m} , y dos vértices de la gráfica de la torre son adyacentes si y solo si los bordes correspondientes del gráfico bipartito completo comparten un punto final común. ^{[2] [17]} En esta vista, un borde en el gráfico 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 gráfico bipartito es un subgrafo de un gráfico bipartito completo y, en consecuencia, cualquier gráfico lineal de un gráfico bipartito es un subgrafo inducido de un gráfico de torre. ^[18] Los gráficos lineales de los gráficos bipartitos son perfectos : en ellos, y en cualquiera de sus subgrafos inducidos, el número de colores necesarios en cualquier coloración de vértices es el mismo que el número de vértices en el subgrafo completo más grande . Los gráficos lineales de gráficos bipartitos forman una familia importante de gráficos perfectos: son una de las pocas familias utilizadas por Chudnovsky et al. (2006) para caracterizar las gráficas perfectas y mostrar que cada gráfica sin agujeros impares ni antiagujeros impares es perfecta. ^[19] En particular, las gráficas de la torre son perfectas en sí mismas.

8 colores de un gráfico de tablero de ajedrez obtenido de una tabla de Cayley de un grupo finito

Debido a que la gráfica de una torre es perfecta, la cantidad de colores necesarios en cualquier coloración de la gráfica es justo el tamaño de su camarilla más grande. Las camarillas del gráfico de una torre son los subconjuntos de una sola fila o una sola columna, y el mayor de ellos tiene un tamaño máximo ( m , n ) , por lo que este también es el número cromático del gráfico. Una coloración n del gráfico de una torre de n × n puede interpretarse como un cuadrado latino : describe una forma de llenar las filas y columnas de una cuadrícula de n × n con n valores diferentes de tal manera que no aparezca el mismo valor. dos veces en cualquier fila o columna. ^[20] De la misma manera, una coloración del gráfico de una torre rectangular corresponde a un rectángulo latino . ^[21] Aunque encontrar una coloración óptima del gráfico de una torre es sencillo, es NP-completo determinar si una coloración parcial se puede extender a una coloración de todo el gráfico (este problema se llama extensión de precoloración ). De manera equivalente, es NP-completo determinar si un cuadrado latino parcial se puede completar en un cuadrado latino completo. ^[22]

Independencia

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

Un conjunto independiente en el gráfico de una torre es un conjunto de vértices, de los cuales no hay dos que pertenezcan a la misma fila o columna del gráfico; en términos de ajedrez, corresponde a una colocación de torres de las cuales no hay dos que se ataquen entre sí. Los gráficos perfectos también pueden describirse como gráficos 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 gráfico en un número mínimo de camarillas. En el gráfico de una torre, los conjuntos de filas o los conjuntos de columnas (el que tenga menos conjuntos) forman esa partición óptima. Por lo tanto, el tamaño del conjunto independiente más grande en el gráfico es min( m , n ) . ^[1]

Las gráficas de la torre están bien cubiertas : cada conjunto independiente en la gráfica de una torre se puede extender a un conjunto independiente máximo, y cada conjunto independiente máximo en la gráfica de una torre tiene el mismo tamaño, min( m , n ) . ^[23]

Dominación

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

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

hamiltonicidad

La gráfica de cada torre contiene un ciclo hamiltoniano . ^[26] Sin embargo, estos ciclos pueden implicar movimientos entre cuadrados que están muy separados dentro de una sola fila o columna del tablero de ajedrez. En cambio, el estudio de los "giros de la torre", en las matemáticas del ajedrez, generalmente se ha concentrado en un caso especial de estos ciclos hamiltonianos donde la torre está restringida a moverse sólo a casillas adyacentes. Estos recorridos de torre de un solo paso sólo existen en tableros con un número par de casillas. Desempeñan un papel central en la demostración 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] Aparecen junto con los recorridos de los caballeros en el primer trabajo que analiza los recorridos de las piezas de ajedrez, el Kavyalankara de Rudrata en sánscrito del siglo IX . ^[28]

Espectro

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

En otros gráficos

Las gráficas para las cuales los vecinos de cada vértice inducen una gráfica de torre se han denominado localmente grilla . Los ejemplos incluyen los gráficos de Johnson , para los cuales los vecinos de cada vértice forman el gráfico de una torre. Se conocen otros ejemplos y, para algunas gráficas de torre, se conoce una clasificación completa. Por ejemplo, hay dos gráficas cuyas vecindades son todas gráficas de torre: son la gráfica de Johnson y la gráfica complementaria de la gráfica de una torre. ^[30] ${\displaystyle J(n,k)}$ ${\displaystyle k\times (n-k)}$ ${\displaystyle 3\times 3}$ ${\displaystyle J(6,3)}$ ${\displaystyle 4\times 4}$

Ver también

• Complejo de tablero de ajedrez , el complejo de independencia de la gráfica de la torre
• Gráfico de rey , gráfico de caballo , gráfico de reina y gráfico de alfil , otros cuatro gráficos definidos a partir de los movimientos de las piezas de ajedrez
• Gráfico de celosía , el gráfico de adyacencias horizontales y verticales de cuadrados en un tablero de ajedrez

Referencias

1. , 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 , señor  1673351.
2. Stones, Douglas S. (2010), "Las muchas 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
3. Azizoğlu, M. Cemil; Eğecioğlu, Ömer (2003), "Conjuntos extremos que minimizan el límite normalizado de dimensión en gráficos de Hamming", Revista SIAM de Matemáticas Discretas , 17 (2): 219–236, doi :10.1137/S0895480100375053, SEÑOR  2032290.
4. Goethals, J.-M.; Seidel, JJ (1970), "Gráficos fuertemente regulares derivados de diseños combinatorios", Canadian Journal of Mathematics , 22 (3): 597–614, doi : 10.4153/CJM-1970-067-9 , MR  0282872, S2CID  199082328.
5. Herzberg, Agnès M .; Murty, M. Ram (2007), "Sudoku cuadrados y polinomios cromáticos" (PDF) , Avisos de la Sociedad Estadounidense de Matemáticas , 54 (6): 708–717, SEÑOR  2327972
6. Matschke, Benjamín; Pfeifle, Julián; Pilaud, Vincent (2011), "Politopos vecinos prodsimpliciales", Geometría discreta y computacional , 46 (1): 100–131, arXiv : 0908.4177 , doi : 10.1007/s00454-010-9311-y, MR  2794360, S2CID  2070310
7. Moore, Doug (1992), "Understanding simploids", en Kirk, David (ed.), Graphics Gems III , Academic Press , págs. 250-255, doi :10.1016/b978-0-08-050755-2.50057-9
8. Moon, JW (1963), "En el gráfico lineal del bigrafo completo", Annals of Mathematical Statistics , 34 (2): 664–667, doi : 10.1214/aoms/1177704179.
9. Hoffman, AJ (1964), "En el gráfico lineal del gráfico bipartito completo", Annals of Mathematical Statistics , 35 (2): 883–885, doi : 10.1214/aoms/1177703593 , MR  0161328.
10. Fiala, Nick C.; Haemers, Willem H. (2006), "Gráficos 5 cromáticos fuertemente regulares", Matemáticas discretas , 306 (23): 3083–3096, doi : 10.1016/j.disc.2004.03.023 , MR  2273138.
11. 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  2953786. Traducido 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)".
12. 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..
13. 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 de la gráfica de la torre, y la discusión anterior sobre la ecuación para el orden de este grupo. ${\displaystyle n\times n}$
14. Biggs, Norman (1974), "La simetría de los gráficos lineales", Utilitas Mathematica , 5 : 113–121, SEÑOR  0347684.
15. Esto se desprende de la definición de la gráfica de la torre como gráfica de producto cartesiano, junto con la Proposición 4 de Broere, Izak; Hattingh, Johannes H. (1990), "Productos de gráficos circulantes", Quaestiones Mathematicae , 13 (2): 191–216, doi :10.1080/16073606.1990.9631612, SEÑOR  1068710.
16. Gris, R.; Macpherson, D. (2010), "Gráficos 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.
17. Para conocer la equivalencia entre productos cartesianos de gráficas completas y gráficas lineales de gráficas bipartitas completas, consulte de Werra, D.; Hertz, A. (1999), "Sobre la perfección de sumas de gráficas" (PDF) , Matemáticas discretas , 195 (1–3): 93–101, doi : 10.1016/S0012-365X(98)00168-X , MR  1663807.
18. de Werra y Hertz (1999).
19. Chudnovsky, María ; Robertson, Neil ; Seymour, Pablo ; Thomas, Robin (2006), "El teorema del grafo perfecto fuerte" (PDF) , Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi :10.4007/annals.2006.164.51, JSTOR  20159988, S2CID  119151552.
20. Para conocer la equivalencia entre gráficos bipartitos completos con coloración de bordes y cuadrados latinos, consulte, por ejemplo, LeSaulnier, Timothy D.; Stocker, Cristóbal; Wenger, Paul S.; West, Douglas B. (2010), "Coincidencia de arcoíris en gráficos con bordes coloreados", Electronic Journal of Combinatorics , 17 (1): Nota 26, 5, doi : 10.37236/475 , MR  2651735.
21. Stones, Douglas S. (2010), "Las muchas 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
22. Colbourn, Charles J. (1984), "La complejidad de completar cuadrados latinos parciales", Matemáticas aplicadas discretas , 8 (1): 25–30, doi : 10.1016/0166-218X(84)90075-1 , SEÑOR  0739595.
23. Para obtener una declaración equivalente a la propiedad bien cubierta de las gráficas de torre, en términos de coincidencias en gráficas bipartitas completas, consulte Lesk, M.; Plummer, Doctor en Medicina; Pulleyblank, WR (1984), "Equi-matchable Graphs", en Bollobás, Béla (ed.), Teoría de grafos y combinatoria: Actas de la Conferencia Combinatoria de Cambridge, en honor a Paul Erdös , Londres: Academic Press, págs. 254, señor  0777180.
24. Yaglom, soy ; Yaglom, IM (1987), "Solución al problema 34b", Desafiando problemas matemáticos con soluciones elementales, Dover, p. 77, ISBN 9780486318578.
25. Burchett, Pablo; Carril, David; Lachniet, Jason (2009), " K -dominación y k -dominación de tuplas en la gráfica de la torre y otros resultados", Congressus Numerantium , 199 : 187–204.
26. Hurley, CB; Oldford, RW (febrero de 2011), "Gráficos como infraestructura de navegación para espacios de datos de alta dimensión", Estadísticas computacionales , 26 (4): 585–612, doi :10.1007/s00180-011-0228-6, S2CID  54220980
27. Watkins, John J. (2004), En todos los ámbitos: las matemáticas de los problemas del tablero de ajedrez , Princeton University Press, p. 12, ISBN 9780691130620
28. Murray, HJR (enero de 1902), "La gira del caballero: antiguo y oriental", The British Chess Magazine , vol. 22, núm. 1, págs. 1 a 7
29. Doob, Michael (1970), "Sobre la caracterización de ciertos gráficos con cuatro valores propios según sus espectros", Álgebra lineal y sus aplicaciones , 3 (4): 461–482, doi : 10.1016/0024-3795(70)90037-6 , Señor  0285432
30. 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, SEÑOR  1072157; véanse en particular las págs. 89 y 90

enlaces externos

• Weisstein, Eric W. , "Gráfico de torres", MathWorld