Producto de reemplazo

{\displaystyle G\circ H} — El producto de reemplazo $G\circ H$ de $K 6$ y $C 5$ .

En teoría de grafos , el producto de reemplazo de dos grafos es un producto de grafos que puede usarse para reducir el grado de un grafo manteniendo su conectividad . ^{[ 1 ]}

Supongamos que $G$ es un grafo $d$ - regular y $H$ es un grafo $e -regular con conjunto de vértices$ ${0, \dots,$ $d$ $- 1}.$ Sea $R$ el producto de reemplazo de $G$ y $H.$ El conjunto de vértices de $R$ es el producto cartesiano $V$ $($ $G$ $) \times$ $V$ $($ $H$ $)$ . Para cada vértice $u$ en $V$ $($ $G$ $)$ y para cada arista $($ $i$ $,$ $j$ $)$ en $E$ $($ $H$ $)$ , el vértice $($ $u$ $,$ $i$ $)$ es adyacente a $($ $u$ $,$ $j$ $)$ en $R$ . Además, para cada arista $($ $u$ $,$ $v$ $)$ en $E$ $($ $G$ $)$ , si $v$ es el $i$ -ésimo vecino de $u$ y $u$ es el $j$ -ésimo vecino de $v$ , el vértice $($ $u$ $,$ $i$ $)$ es adyacente a $($ $v$ $,$ $j$ $)$ en $R$ .

Si $H$ es un grafo $e$ -regular, entonces $R$ es un grafo $(e +1)$ -regular.

Referencias

↑ Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (7 de agosto de 2006). "Grafos expansores y sus aplicaciones" . Boletín de la Sociedad Matemática Americana . 43 (4): 439– 562. doi : 10.1090/S0273-0979-06-01126-8 .

Enlaces externos

Trevisan, Luca (7 de marzo de 2011). "CS359G Lección 17: El producto en zigzag" . Recuperado el 16 de diciembre de 2014 .

[1] Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (7 de agosto de 2006). "Grafos expansores y sus aplicaciones" . Boletín de la Sociedad Matemática Americana . 43 (4): 439– 562. doi : 10.1090/S0273-0979-06-01126-8 .

[ 1 ]