Producto modular de grafos

En teoría de grafos , el producto modular de los grafos $G$ y $H$ es un grafo formado al combinar $G$ y $H$ que tiene aplicaciones en el isomorfismo de subgrafos . Es uno de los diversos tipos de productos de grafos que se han estudiado, generalmente utilizando el mismo conjunto de vértices (el producto cartesiano de los conjuntos de vértices de los dos grafos $G$ y $H$ ), pero con reglas diferentes para determinar qué aristas incluir.

Definición

El conjunto de vértices del producto modular de $G$ y $H$ es el producto cartesiano $V (G) \times V (H)$ . Dos vértices cualesquiera $(u, v)$ y $(u', v')$ son adyacentes en el producto modular de $G$ y $H$ si y solo si $u$ es distinto de $u'$ , $v$ es distinto de $v'$ y se cumple que

$u$ es adyacente a $u'$ y $v$ es adyacente a $v'$ , o
$u$ no es adyacente a $u'$ y $v$ no es adyacente a $v'$ .

Aplicación al isomorfismo de subgrafos

Las camarillas en el grafo producto modular corresponden a isomorfismos de subgrafos inducidos de $G$ y $H.$ Por lo tanto, el grafo producto modular puede utilizarse para reducir los problemas de isomorfismo de subgrafos inducidos a problemas de búsqueda de camarillas en grafos. Específicamente, el subgrafo inducido común máximo de $G$ y $H$ corresponde a la camarilla máxima en su producto modular. Si bien los problemas de encontrar los subgrafos inducidos comunes más grandes y de encontrar las camarillas máximas son ambos NP-completos , esta reducción permite aplicar algoritmos de búsqueda de camarillas al problema del subgrafo común.

Referencias

Barrow, H.; Burstall, R. (1976), "Isomorfismo de subgrafos, estructuras relacionales coincidentes y camarillas máximas", Information Processing Letters , 4 (4): 83– 84, doi : 10.1016/0020-0190(76)90049-1.
Levi, G. (1973), "Una nota sobre la derivación de subgrafos comunes máximos de dos grafos dirigidos o no dirigidos", Calcolo , 9 (4): 341–352 , doi : 10.1007/BF02575586.
Vizing, VG (1974), "Reducción del problema del isomorfismo y la entrada isomorfa a la tarea de encontrar la no densidad de un grafo", Actas de la 3.ª Conferencia de la Unión sobre Problemas de Cibernética Teórica , pág. 124.