En teoría de grafos , una cobertura plana de un gráfico finito G es una cobertura finita de G que es en sí misma una gráfica plana . Todo gráfico que pueda incrustarse en el plano proyectivo tiene una cubierta plana; Una conjetura sin resolver de Seiya Negami afirma que estos son los únicos gráficos con cubiertas planas. [1]
La existencia de una cubierta plana es una propiedad de grafo cerrado menor , [2] y, por lo tanto, puede caracterizarse por un número finito de menores prohibidos , pero se desconoce el conjunto exacto de menores prohibidos. Por la misma razón, existe un algoritmo de tiempo polinomial para probar si un gráfico dado tiene una cobertura plana, pero se desconoce una descripción explícita de este algoritmo.
Un mapa de cobertura de un gráfico C a otro gráfico H puede describirse mediante una función f desde los vértices de C sobre los vértices de H que, para cada vértice v de C , da una biyección entre los vecinos de v y los vecinos de f. ( v ). [3] Si H es un gráfico conexo , cada vértice de H debe tener el mismo número de preimágenes en C ; [2] este número se llama capa del mapa y C se llama gráfico de cobertura de G. Si C y H son finitos y C es un gráfico plano , entonces C se llama cobertura plana de H.
La gráfica del dodecaedro tiene una simetría que asigna cada vértice al vértice antípoda. El conjunto de pares de vértices antípodas y sus adyacencias puede verse en sí mismo como un gráfico, el gráfico de Petersen . El dodecaedro forma una cubierta plana de este grafo no plano. [4] Como muestra este ejemplo, no todos los gráficos con una cobertura plana son en sí mismos planos. Sin embargo, cuando un gráfico plano cubre uno no plano, la capa debe ser un número par . [5]
La gráfica de un k -prisma gonal tiene 2 k vértices y es plana con dos k -caras gonales y k caras cuadriláteras. Si k = ab , con a ≥ 2 y b ≥ 3, entonces tiene un mapa de cobertura de una capa a un prisma b -fonal, en el que dos vértices del k -prisma están asignados al mismo vértice del b -prisma si ambos pertenecen a la misma cara k -gonal y la distancia de uno a otro es múltiplo de b . Por ejemplo, el prisma dodecagonal puede formar una cubierta de 2 capas del prisma hexagonal , una cubierta de 3 capas del cubo o una cubierta de 4 capas del prisma triangular . Estos ejemplos muestran que un gráfico puede tener muchas coberturas planas diferentes y puede ser la cobertura plana de muchos otros gráficos. Además, muestran que la capa de una cubierta plana puede ser arbitrariamente grande. No son las únicas coberturas que involucran prismas: por ejemplo, el prisma hexagonal también puede cubrir un grafo no plano, el grafo de utilidad K 3,3 , identificando pares de vértices antípodas. [6]
Si un gráfico H tiene una cobertura plana, también la tiene cada gráfico menor de H. [2] Se puede formar una G menor de H eliminando aristas y vértices de H y contrayendo aristas de H. El gráfico de cobertura C se puede transformar de la misma manera: para cada borde o vértice eliminado en H , elimine su preimagen en C , y para cada borde o vértice contraído en H , contraiga su preimagen en C. El resultado de aplicar estas operaciones a C es un menor de C que cubre G . Dado que cada menor de un gráfico plano es en sí mismo plano, esto da una cobertura plana del menor G.
Debido a que los gráficos con cubiertas planas están cerrados bajo la operación de tomar menores, del teorema de Robertson-Seymour se deduce que pueden caracterizarse por un conjunto finito de menores prohibidos . [7] Un gráfico es un menor prohibido para esta propiedad si no tiene cobertura plana, pero todos sus menores sí tienen coberturas planas. Esta caracterización se puede utilizar para probar la existencia de un algoritmo de tiempo polinómico que prueba la existencia de una cubierta plana, buscando cada uno de los menores prohibidos y arrojando que existe una cubierta plana sólo si esta búsqueda no logra encontrar ninguno de ellos. [8] Sin embargo, debido a que no se conoce el conjunto exacto de menores prohibidos para esta propiedad, esta prueba de existencia no es constructiva y no conduce a una descripción explícita del conjunto de menores prohibidos o del algoritmo basado en ellos. [9]
Otra operación gráfica que preserva la existencia de una cobertura plana es la transformada Y-Δ , que reemplaza cualquier vértice de grado tres de una gráfica H por un triángulo que conecta sus tres vecinos. [2] Sin embargo, lo contrario de esta transformación, una transformada Δ-Y, no necesariamente preserva las cubiertas planas.
Además, una unión disjunta de dos gráficos que tienen cubiertas también tendrá una cubierta, formada como la unión disjunta de los gráficos de cobertura. Si las dos fundas tienen la misma tela entre sí, entonces ésta será también la tela de su unión.
¿Todo gráfico conectado con una cubierta plana tiene una incrustación en el plano proyectivo?
Si un gráfico H tiene una incrustación en el plano proyectivo , entonces necesariamente tiene una cobertura plana, dada por la preimagen de H en la doble cobertura orientable del plano proyectivo, que es una esfera. Negami (1986) demostró, por el contrario, que si un gráfico conexo H tiene una cubierta plana de dos capas, entonces H debe estar incrustado en el plano proyectivo. [10] La suposición de que H es conexo es necesaria aquí, porque una unión disjunta de grafos proyectivo-planares puede no ser en sí misma proyectiva-planar [11] pero aún tendrá una cubierta plana, la unión disjunta de las cubiertas dobles orientables.
Una cobertura regular de un grafo H es aquella que proviene de un grupo de simetrías de su grafo de cobertura: las preimágenes de cada vértice en H son una órbita del grupo. Negami (1988) demostró que todo grafo conectado con una cubierta regular plana puede incrustarse en el plano proyectivo. [12] Basándose en estos dos resultados, conjeturó que, de hecho, todo gráfico conectado con una cubierta plana es proyectivo. [13] A partir de 2013, esta conjetura sigue sin resolverse. [14] También se conoce como la "conjetura 1-2-∞" de Negami, porque puede reformularse afirmando que la capa mínima de una cubierta plana, si existe, debe ser 1 o 2. [15]
Al igual que los grafos con cubiertas planas, los grafos con incrustaciones de planos proyectivos pueden caracterizarse por menores prohibidos. En este caso se conoce el conjunto exacto de menores prohibidos: son 35. 32 de ellos están conectados, y uno de estos 32 gráficos aparece necesariamente como menor en cualquier gráfico plano no proyectivo conectado. [16] Desde que Negami hizo su conjetura, se ha demostrado que 31 de estos 32 menores prohibidos no tienen cubiertas planas o pueden reducirse mediante transformaciones Y-Δ a un gráfico más simple en esta lista. [17] El único gráfico restante para el que esto aún no se ha hecho es K 1,2,2,2 , un gráfico de siete vértices que forma el esqueleto de una pirámide octaédrica de cuatro dimensiones . Si se pudiera demostrar que K 1,2,2,2 no tiene cubiertas planas, esto completaría la prueba de la conjetura. Por otro lado, si la conjetura es falsa, K 1,2,2,2 sería necesariamente su contraejemplo más pequeño. [18]
Una conjetura relacionada de Michael Fellows , ahora resuelta, se refiere a los emuladores planos , una generalización de cubiertas planas que mapea vecindarios de gráficos de manera sobreyectiva en lugar de biyectiva. [19] Los gráficos con emuladores planos, como aquellos con cubiertas planas, están cerrados bajo transformaciones menores y Y-Δ. [20] En 1988, independientemente de Negami, Fellows conjeturó que los gráficos con emuladores planos son exactamente los gráficos que se pueden incrustar en el plano proyectivo. [21] La conjetura es cierta para emuladores regulares , ya que proviene de automomorfismos del gráfico de cobertura subyacente, por un resultado análogo al resultado de Negami (1988) para coberturas planas regulares. [22] Sin embargo, varios de los 32 menores prohibidos conectados para gráficos planos proyectivos resultan tener emuladores planos. [23] Por lo tanto, la conjetura de Fellows es falsa. Encontrar un conjunto completo de menores prohibidos para la existencia de emuladores planos sigue siendo un problema abierto. [24]