Producto fuerte de gráficos.

Operación binaria en teoría de grafos

El gráfico del rey , un fuerte producto de dos gráficos de trayectorias.

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

Un ejemplo de 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 trayectoria. Las descomposiciones de gráficos planos y clases de gráficos relacionados en productos fuertes se han utilizado como herramienta central para probar 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 las gráficas G y H es una gráfica tal que ^[2] el conjunto de vértices de G ⊠ H es el producto cartesiano V ( G ) × V ( H ) ; y los vértices distintos ( u , u' ) y ( v , v' ) son adyacentes en G ⊠ H si y solo si :

u = v y u' es adyacente a v' , o

u' = v' y u es adyacente a v , o

u es adyacente a v y u' es adyacente a v' .

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

Por ejemplo, el gráfico del rey , un gráfico cuyos vértices son cuadrados de un tablero de ajedrez y cuyos bordes representan posibles movimientos de un rey de ajedrez, es un fuerte producto de dos gráficos de trayectoria . Sus aristas horizontales provienen del producto cartesiano y sus aristas diagonales provienen del producto tensorial de los mismos dos caminos. Juntos, estos dos tipos de bordes forman todo el producto resistente. ^[3]

Propiedades y aplicaciones

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

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

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

El fuerte producto de un gráfico de ciclo de 7 vértices y un gráfico completo de 4 vértices , ha sido sugerido como una posibilidad para un gráfico biplanar de 10 cromáticos que mejoraría los límites conocidos del problema Tierra-Luna ; Otro ejemplo sugerido es el gráfico obtenido eliminando cualquier vértice de . En ambos casos, el número de vértices en estos gráficos 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 gráficos son biplanares. ^[20] ${\displaystyle C_{7}\boxtimes K_{4}}$ ${\displaystyle C_{5}\boxtimes K_{4}}$

Referencias

1. 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.
2. Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Gráficos y su producto cartesiano , AK Peters, ISBN 978-1-56881-429-2.
3. Berend, Daniel; Koraj, Efraín; Zucker, Shira (2005), "Dos anticolores de gráficos planos y relacionados" (PDF) , Conferencia internacional de 2005 sobre análisis de algoritmos , matemáticas discretas y procedimientos de informática teórica, Nancy: Asociación de Matemáticas Discretas e Informática Teórica, págs. 335–341, SEÑOR  2193130.
4. 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
5. Ueckerdt, Torsten; Madera, David R .; Yi, Wendy (2022), "Un teorema de estructura de producto de gráfico plano mejorado", Electronic Journal of Combinatorics , 29 (2), artículo n.º 2.51, arXiv : 2108.00198 , doi : 10.37236/10614 , MR  4441087, S2CID  236772054
6. 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
7. Gawrychowski, Pawel; Janczewski, Wojciech (2022), "Etiquetado de adyacencia más simple para gráficos planos 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 , Sociedad de Matemáticas Industriales y Aplicadas, págs. 24–36, doi :10.1137/1.9781611977066.3 , S2CID  245738461
8. Esperet, Louis; Joret, Gwenaël; Morin, Pat (2020), Gráficos universales dispersos para planaridad , arXiv : 2010.05779
9. Huynh, Tony; Mohar, Bojan ; Samal, Robert; Thomassen, Carsten ; Wood, David R. (2021), Universalidad en clases de gráficos cerrados menores , arXiv : 2109.00327
10. Dujmović, Vida ; Espéret, Louis; Joret, Gwenaël; Walczak, Bartosz; Wood, David R. (2020), "Los gráficos planos tienen un número cromático no repetitivo acotado", Avances en combinatoria : artículo n.º 5, 11, MR  4125346
11. Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021), "Límites mejorados para coloraciones centradas", Avances en combinatoria , artículo n.º 8, arXiv : 1907.04586 , doi :10.19086/aic.27351, MR  4309118, S2CID  195874032
12. Morin, Pat (2021), "Un algoritmo rápido para la estructura del producto de gráficos planos", Algorithmica , 83 (5): 1544–1558, arXiv : 2004.02530 , doi :10.1007/s00453-020-00793-5, MR  4242109 , S2CID  254028754
13. Bosé, Prosenjit ; Morín, Pat ; Odak, Saeed (2022), Un algoritmo óptimo para la estructura del producto de gráficos planos , arXiv : 2202.08870
14. Distel, Marc; Hickingbotham, Robert; Huynh, Tony; Wood, David R. (2022), "Estructura de producto mejorada para gráficos en superficies", Matemáticas discretas e informática teórica , 24 (2): Documento n.º 6, arXiv : 2112.10025 , doi :10.46298/dmtcs.8877, MR  4504777 , S2CID  245335306
15. Dujmović, Vida ; Espéret, Louis; Morín, Pat ; Walczak, Bartosz; Wood, David R. (2022), "Gráficos agrupados de 3 colores de grado acotado", Combinatoria, probabilidad y computación , 31 (1): 123–135, arXiv : 2002.11721 , doi : 10.1017 / s0963548321000213, MR  4356460, S2CID  2115328 24
16. Dujmović, Vida ; Morín, Pat ; Wood, David R. (2019), Estructura gráfica del producto para clases cerradas no menores , arXiv : 1907.05168
17. 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
18. 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
19. Eppstein, David ; Havvaei, Elham (2020), "Reconocimiento parametrizado del poder de la hoja 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
20. Gethner, Ellen (2018), "A 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 de matemáticas, Springer International Publishing, págs. 115–133, doi :10.1007/978-3-319-97686-0_11, Señor  3930641