Producto enraizado de grafos

En la teoría matemática de grafos , el producto enraizado (o producto peine ) de un grafo G y un grafo enraizado H se define de la siguiente manera: tomar | V ( G ) | copias de H y para cada vértice v _i de G , identificar v _i con el nodo raíz de la i -ésima copia de H.

Más formalmente, suponiendo que

${\displaystyle {\begin{aligned}V(G)&=\{g_{1},\ldots ,g_{n}\},\\V(H)&=\{h_{1},\ldots ,h_{m}\},\end{aligned}}}$

y que el nodo raíz de H es h ₁ , definimos

${\displaystyle G\circ H:=(V,E)}$,

dónde

${\displaystyle V=\left\{(g_{i},h_{j}):1\leq i\leq n,1\leq j\leq m\right\}}$

y

${\displaystyle E={\Bigl \{}{\bigl (}(g_{i},h_{1}),(g_{k},h_{1}){\bigr )}:(g_{i},g_{k})\in E(G){\Bigr \}}\cup \bigcup _{i=1}^{n}{\Bigl \{}{\bigl (}(g_{i},h_{j}),(g_{i},h_{k}){\bigr )}:(h_{j},h_{k})\in E(H){\Bigr \}}}$.

Si G también tiene su raíz en g ₁ , se puede considerar que el producto mismo tiene su raíz en ( g ₁ , h ₁ ) . El producto con raíz es un subgrafo del producto cartesiano de esos mismos dos grafos.

El producto enraizado es especialmente relevante para los árboles , ya que el producto enraizado de dos árboles es otro árbol. Por ejemplo, Koh et al. (1980) utilizaron productos enraizados para encontrar numeraciones elegantes para una amplia familia de árboles.

Si H es un grafo completo de dos vértices K ₂ , entonces para cualquier grafo G , el producto enraizado de G y H tiene un número de dominación exactamente la mitad de su número de vértices. Todo grafo conexo en el que el número de dominación es la mitad del número de vértices surge de esta manera, con la excepción del grafo ciclo de cuatro vértices . Estos grafos pueden usarse para generar ejemplos en los que se cumple exactamente la cota de la conjetura de Vizing , una desigualdad no probada entre el número de dominación de los grafos en un producto de grafos diferente, el producto cartesiano de grafos ( Fink et al. 1985 ) . También son grafos bien cubiertos .

• Godsil, CD ; McKay, BD (1978), "Un nuevo producto de grafos y su espectro" (PDF) , Bull. Austral. Math. Soc. , 18 (1): 21–28 , doi : 10.1017/S0004972700007760 , MR 0494910 .
• Fink, JF; Jacobson, MS; Kinch, LF; Roberts, J. (1985), "Sobre grafos cuyo número de dominación es la mitad de su orden", Period. Math. Hungar. , 16 (4): 287– 293, doi : 10.1007/BF01848079 , MR 0833264 .
• Koh, KM; Rogers, DG; Tan, T. (1980), "Productos de árboles elegantes", Matemáticas Discretas , 31 (3): 279– 292, doi : 10.1016/0012-365X(80)90139-9 , MR 0584121 .