Gráfico de Rook

Moon (1963) y Hoffman (1964) observan que el${\displaystyle m\times n}$el grafo de la torre (o equivalentemente, como lo describen, el grafo de líneas del grafo bipartito completo)${\displaystyle K_{m,n}}$) tiene todas las siguientes propiedades:

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

Demuestran que, excepto en el caso${\displaystyle m=n=4}$Estas propiedades caracterizan de manera única el 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 vértices que pasa por cada par de vértices no adyacentes. ^{[ 8 ] [ 9 ]}

Cuando${\displaystyle m=n}$, estas condiciones pueden abreviarse indicando que un${\displaystyle n\times n}$El grafo de Rook es un grafo fuertemente regular con parámetros ${\displaystyle \operatorname {srg} (n^{2},2n-2,n-2,2)}$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 grafo fuertemente regular con estos parámetros debe ser un${\displaystyle n\times n}$gráfico de torre, a menos que${\displaystyle n=4}$. ^{[ 8 ] [ 9 ]}

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

Los grafos de Rook son transitivos en vértices , lo que significa que tienen simetrías que llevan cada vértice a todos los demás vértices. Esto implica que cada vértice tiene un número igual de aristas: son${\displaystyle (m+n-2)}$- regular . Los gráficos de la torre son los únicos gráficos regulares formados a partir de los movimientos de las piezas de ajedrez estándar de esta manera. ^{[ 12 ]} Cuando${\displaystyle m\neq n}$, 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${\displaystyle m!n!}$elementos. Cuando${\displaystyle m=n}$, el gráfico tiene simetrías adicionales que intercambian las filas y columnas, por lo que el número de automorfismos es${\displaystyle 2n!^{2}}$. ^{[ 13 ]}

Dos vértices cualesquiera en el grafo de la torre están a una o dos distancias entre sí, según sean adyacentes o no adyacentes, respectivamente. Dos vértices no adyacentes pueden transformarse en otros dos vértices no adyacentes 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, dos vértices adyacentes también pueden transformarse entre sí mediante una simetría, por lo que el grafo es transitivo en distancia . ^{[ 14 ]}

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

Los grafos de torre cuadrada son homogéneos conectados , lo que significa que todo isomorfismo entre dos subgrafos inducidos conectados puede extenderse a un automorfismo del grafo completo. ^{[ 16 ]}

El grafo de una torre también puede verse como el grafo de líneas de un grafo bipartito completo K _{n , m} — es decir, tiene un vértice por 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 extremo común. ^{[ 2 ] [ 17 ]} En esta visión, una arista en el grafo bipartito completo desde el i -ésimo vértice de un lado de la bipartición hasta el j -ésimo vértice del otro lado corresponde a una casilla del tablero de ajedrez con coordenadas ( i , j ) . ^{[ 1 ]}

Cualquier grafo bipartito es un subgrafo de un grafo bipartito completo, y correspondientemente cualquier grafo de líneas de un grafo bipartito es un subgrafo inducido de un grafo de torre. ^{[ 18 ]} Los grafos de líneas de los 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értices es el mismo que el número de vértices en el subgrafo completo más grande . Los grafos de líneas de los 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 para demostrar que todo grafo sin agujero impar ni antiagujero impar es perfecto. ^{[ 19 ]} En particular, los grafos de torre son perfectos en sí mismos.

Debido a que el grafo de una torre es perfecto, el número de colores necesarios en cualquier coloración del grafo es simplemente el tamaño de su clique más grande. Las cliques de un grafo de torre son los subconjuntos de una sola fila o una sola columna, y el más grande de estos tiene un tamaño max( m , n ) , por lo que este es también el número cromático del grafo. Una n -coloración de un grafo de torre n × n puede interpretarse como un cuadrado latino : describe una forma de llenar las filas y columnas de una cuadrícula n × 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 grafo de torre rectangular corresponde a un rectángulo latino . ^{[ 21 ]} Si bien encontrar una coloración óptima del grafo de una torre es sencillo, determinar si una coloración parcial puede extenderse a una coloración del grafo completo es un problema NP-completo (este problema se denomina extensión de precoloración ). De manera equivalente, determinar si un cuadrado latino parcial puede completarse a un cuadrado latino completo es un problema NP-completo. ^{[ 22 ]}

Un conjunto independiente en un grafo de torres es un conjunto de vértices, ninguno de los cuales pertenece a la misma fila o columna del grafo; en términos de ajedrez, corresponde a una disposición de torres en la que ninguna de ellas ataca a otra. Los grafos perfectos también pueden describirse como aquellos 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 torres, los conjuntos de filas o los conjuntos de columnas (el que tenga menos conjuntos) forman dicha partición óptima. Por lo tanto, el tamaño del conjunto independiente más grande en el grafo es min( m , n ) . ^{[ 1 ]}

Los grafos de Rook son grafos bien cubiertos : cada conjunto independiente en un grafo de Rook puede extenderse a un conjunto independiente máximo, y cada conjunto independiente máximo en un grafo de Rook tiene el mismo tamaño, min( m , n ) . ^{[ 23 ]}

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 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 grafo de la torre, un conjunto k -dominante es un conjunto de vértices cuyos cuadrados correspondientes atacan a todos los demás cuadrados (mediante un movimiento de la 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 -tupla dominantes es el número de k -dominación y el número de k -tupla dominante, respectivamente. En el tablero cuadrado, y para k par , el número de k -dominación es nk /2 cuando n ≥ ( k ² − 2 k )/4 y k < 2 n . De manera similar, el número de k -tupla dominante es n ( k + 1)/2 cuando k es impar y menor que 2 n . ^{[ 25 ]}

Cada grafo de torre contiene un ciclo hamiltoniano . ^{[ 26 ]} Sin embargo, estos ciclos pueden implicar movimientos entre casillas muy distantes dentro de una misma fila o columna del tablero. En cambio, el estudio de los "recorridos de torre", en las matemáticas del ajedrez, se ha centrado 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. Juegan un papel central en la demostración del teorema de Gomory que establece que, si se eliminan dos casillas de colores opuestos de un tablero de ajedrez estándar, las casillas restantes siempre pueden cubrirse con dominós. ^{[ 27 ]} Se presentan junto con los recorridos de caballo en la primera obra que trata sobre recorridos de piezas de ajedrez, el Kavyalankara de Rudrata en sánscrito del siglo IX . ^{[ 28 ]}

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