Producto fuerte de gráficos

En teoría de grafos , el producto fuerte es una forma de combinar dos grafos para formar un grafo más grande. Dos vértices son adyacentes en el producto fuerte cuando provienen de pares de vértices en los grafos factoriales que son adyacentes o idénticos. El producto fuerte es una de varias operaciones de producto de grafos diferentes que se han estudiado en teoría de grafos. El producto fuerte de dos grafos cualesquiera se puede construir como la unión de otros dos productos de los mismos dos grafos, el producto cartesiano de grafos y el producto tensorial de grafos .

Un ejemplo de un producto fuerte es el gráfico del rey , el gráfico de movimientos de un rey de ajedrez sobre un tablero de ajedrez, que puede construirse como un producto fuerte de gráficos de trayectorias. Las descomposiciones de gráficos planares y clases de gráficos relacionadas en productos fuertes se han utilizado como una herramienta central para demostrar muchos otros resultados sobre estos gráficos.

Se debe tener cuidado al encontrar el término producto fuerte en la literatura, ya que también se ha utilizado para denotar el producto tensorial de gráficos. ^[1]

Definición y ejemplo

El producto fuerte $G ⊠ H$ de los grafos $G$ y $H$ es un grafo tal que ^[2] el conjunto de vértices de $G ⊠ H$ es el producto cartesiano $V (G) \times V (H)$ ; y los vértices distintos $(u, u')$ y $(v, v')$ son adyacentes en $G ⊠ H$ si y solo si :

u = v

u'

es adyacente a

v'

, o

u' = v'

u

es adyacente a

v

, o

u

es adyacente a

v

u'

es adyacente a

v'

Es la unión del producto cartesiano y el producto tensorial .

Por ejemplo, el grafo del rey , un grafo cuyos vértices son cuadrados de un tablero de ajedrez y cuyos bordes representan posibles movimientos de un rey de ajedrez, es un producto fuerte de dos grafos de trayectorias . Sus bordes horizontales provienen del producto cartesiano, y sus bordes diagonales provienen del producto tensorial de las mismas dos trayectorias. Juntos, estos dos tipos de bordes conforman el producto fuerte completo. ^[3]

Propiedades y aplicaciones

Cada grafo planar es un subgrafo de un producto fuerte de un camino y un grafo de ancho de árbol como máximo seis. ^[4]^[5] Este resultado se ha utilizado para demostrar que los grafos planares tienen número de cola acotado , ^[4]grafos universales pequeños y esquemas de etiquetado de adyacencia concisos , ^[6]^[7]^[8]^[9] y número cromático no repetitivo acotado ^[10] y número cromático centrado. ^[11] Esta estructura de producto se puede encontrar en tiempo lineal . ^[12]^[13] Más allá de los grafos planares, se han demostrado extensiones de estos resultados para grafos de género acotado , ^[4]^[14] grafos con un menor prohibido que es un grafo de vértice , ^[4] grafos de grado acotado con cualquier menor prohibido, ^[15] y grafos k-planares . ^[16]

El número de camarilla del producto fuerte de dos grafos cualesquiera es igual al producto de los números de camarilla de los dos grafos. ^{[17] Si dos grafos tienen ambos}un ancho gemelo acotado , y además uno de ellos tiene un grado acotado, entonces su producto fuerte también tiene un ancho gemelo acotado. ^[18]

Una potencia de hoja es un gráfico formado a partir de las hojas de un árbol al hacer que dos hojas sean adyacentes cuando su distancia en el árbol es inferior a un umbral determinado . Si es una potencia de hoja de un árbol , entonces se puede encontrar como un subgrafo de un producto fuerte de con un ciclo de vértice. Esta incrustación se ha utilizado en algoritmos de reconocimiento para potencias de hojas. ^[19] ${\estilo de visualización k}$ ${\estilo de visualización G}$ ${\estilo de visualización k}$ ${\estilo de visualización T}$ ${\estilo de visualización T}$ ${\estilo de visualización G}$ ${\estilo de visualización k}$

Se ha sugerido que el producto fuerte de un grafo de ciclo de 7 vértices y un grafo completo de 4 vértices , , es una posibilidad para un grafo biplanar de 10 cromáticos que mejoraría los límites conocidos en el problema Tierra-Luna ; otro ejemplo sugerido es el grafo obtenido al eliminar cualquier vértice de . En ambos casos, el número de vértices en estos grafos es más de 9 veces el tamaño de su conjunto independiente más grande , lo que implica que su número cromático es al menos 10. Sin embargo, no se sabe si estos grafos son biplanares. ^[20] $C_{7}\boxtimes K_{4}$ $C_{5}\boxtimes K_{4}$

Referencias

^ Véase la página 2 de Lovász, László (1979), "Sobre la capacidad de Shannon de un gráfico", IEEE Transactions on Information Theory , IT-25 (1): 1–7, doi :10.1109/TIT.1979.1055985.
^ Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Gráficos y su producto cartesiano , AK Peters, ISBN 978-1-56881-429-2.
^ Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Dos anticoloraciones de gráficos planos y relacionados" (PDF) , Conferencia internacional de 2005 sobre análisis de algoritmos , Actas de Matemáticas discretas y Ciencias de la computación teórica, Nancy: Asociación de Matemáticas discretas y Ciencias de la computación teórica, págs. 335–341, MR 2193130.
^ abcd Dujmović, Vida ; Joret, Gwenaël; Micek, Piotr; Morín, Pat ; Ueckerdt, Torsten; Wood, David R. (2020), "Los gráficos planos tienen un número de cola acotado", Journal of the ACM , 67 (4): art. 22, 38, arXiv : 1904.04791 , doi : 10.1145/3385731, SEÑOR 4148600
^ Ueckerdt, Torsten; Wood, David R .; Yi, Wendy (2022), "Un teorema mejorado de la estructura del producto de grafos planares", Electronic Journal of Combinatorics , 29 (2), número de artículo 2.51, arXiv : 2108.00198 , doi : 10.37236/10614 , MR 4441087, S2CID 236772054
^ Dujmović, Vida ; Espéret, Louis; Gavoille, Cyril; Joret, Gwenaël; Micek, Piotr; Morin, Pat (2021), "Etiquetado de adyacencia para gráficos planos (y más allá)", Journal of the ACM , 68 (6): art. 42, 33, arXiv : 2003.04280 , doi : 10.1145/3477542, SEÑOR 4402353
^ Gawrychowski, Pawel; Janczewski, Wojciech (2022), "Etiquetado de adyacencia más simple para grafos planares con árboles B", en Bringmann, Karl; Chan, Timothy (eds.), 5.º Simposio sobre simplicidad en algoritmos, SOSA@SODA 2022, Conferencia virtual, 10 y 11 de enero de 2022 , Society for Industrial and Applied Mathematics, págs. 24–36, doi :10.1137/1.9781611977066.3, S2CID 245738461
^ Esperet, Louis; Joret, Gwenaël; Morin, Pat (2020), Gráficos universales dispersos para planaridad , arXiv : 2010.05779
^ Huynh, Tony; Mohar, Bojan ; Šámal, Robert; Thomassen, Carsten ; Wood, David R. (2021), Universalidad en clases de grafos menores cerrados , arXiv : 2109.00327
^ Dujmović, Vida ; Esperet, Louis; Joret, Gwenaël; Walczak, Bartosz; Wood, David R. (2020), "Los gráficos planares tienen un número cromático no repetitivo acotado", Advances in Combinatorics : Paper No. 5, 11, MR 4125346
^ Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021), "Límites mejorados para coloraciones centradas", Advances in Combinatorics , artículo n.º 8, arXiv : 1907.04586 , doi : 10.19086/aic.27351, MR 4309118, S2CID 195874032
^ Morin, Pat (2021), "Un algoritmo rápido para la estructura del producto de grafos planares", Algorithmica , 83 (5): 1544–1558, arXiv : 2004.02530 , doi :10.1007/s00453-020-00793-5, MR 4242109, S2CID 254028754
^ Bose, Prosenjit ; Morin, Pat ; Odak, Saeed (2022), Un algoritmo óptimo para la estructura del producto de gráficos planares , arXiv : 2202.08870
^ Distel, Marc; Hickingbotham, Robert; Huynh, Tony; Wood, David R. (2022), "Estructura de producto mejorada para gráficos en superficies", Discrete Mathematics & Theoretical Computer Science , 24 (2): Documento n.º 6, arXiv : 2112.10025 , doi : 10.46298/dmtcs.8877, MR 4504777, S2CID 245335306
^ Dujmović, Vida ; Esperet, Louis; Morin, Pat ; Walczak, Bartosz; Wood, David R. (2022), "Gráficos agrupados de 3 colores de grado acotado", Combinatorics, Probability and Computing , 31 (1): 123–135, arXiv : 2002.11721 , doi :10.1017/s0963548321000213, MR 4356460, S2CID 211532824
^ Dujmović, Vida ; Morin, Pat ; Wood, David R. (2019), Estructura del producto gráfico para clases no cerradas menores , arXiv : 1907.05168
^ Kozawa, Kyohei; Otachi, Yota; Yamazaki, Koichi (2014), "Límites inferiores para el ancho de árbol de los gráficos de productos", Matemáticas aplicadas discretas , 162 : 251–258, doi : 10.1016/j.dam.2013.08.005 , MR 3128527
^ Capo, Édouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width II: clases pequeñas", Teoría combinatoria , 2 (2): P10:1–P10:42, arXiv : 2006.09877 , doi :10.5070/C62257876, MR 4449818
^ Eppstein, David ; Havvaei, Elham (2020), "Reconocimiento de potencia de hoja parametrizada mediante incrustación en productos gráficos", Algorithmica , 82 (8): 2337–2359, arXiv : 1810.02452 , doi :10.1007/s00453-020-00720-8, MR 4132894, S2CID 254032445
^ Gethner, Ellen (2018), "Hasta la Luna y más allá", en Gera, Ralucca ; Haynes, Teresa W. ; Hedetniemi, Stephen T. (eds.), Teoría de grafos: conjeturas favoritas y problemas abiertos, II , Libros de problemas en matemáticas, Springer International Publishing, págs. 115–133, doi :10.1007/978-3-319-97686-0_11, MR 3930641