Producto de raíz

En la teoría de grafos, el producto raíz de un gráfico G y un gráfico raíz H se define de la siguiente manera: tomar | V ( G )| copias del gráfico H y para cada vértice del gráfico G , nos identificamos con el vértice raíz de la i -ésima copia de H. $v_{i}$ $v_{i}$

Más formal. Supongamos que V ( G ) = { g 1 , ..., g n }, V ( H ) = { h 1 , ..., h m } y que la raíz de la gráfica H es . Definamos el producto $h_1$

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\))

E=\left\{((g_{i},h_{1}),(g_{k},h_{1})):(g_{i},g_{k})\en E( G)\right\}\cup \bigcup _{i=1}^{n}\left\{((g_{i},h_{j}),(g_{i},h_{k})): (h_{j},h_{k})\en E(H)\derecha\}

Si el grafo G también está enraizado con raíz g 1 , se puede considerar el producto en sí como un grafo enraizado con raíz ( g 1 , h 1 ). El producto raíz es un subgráfico del producto directo de los mismos dos gráficos.

Aplicaciones

El producto raíz es especialmente relevante para los árboles , ya que el producto raíz de dos árboles volverá a ser un árbol. Por ejemplo, Koch y otros (1980) utilizaron productos de raíz para encontrar una numeración elegante para una amplia familia de árboles.

Si H es un grafo completo con dos vértices K 2 , entonces para cualquier grafo G la raíz producto de los gráficos G y H tiene un número de dominancia igual a exactamente la mitad del número de sus vértices. Cualquier gráfico conexo en el que el número de dominancia es igual a la mitad de los vértices se obtiene de esta forma, excepto un ciclo con cuatro vértices. Estos gráficos se pueden utilizar para generar ejemplos en los que un producto gráfico directo alcanza el límite de la conjetura de Vizing , una desigualdad no demostrada entre el número de dominancia de gráficos en diferentes productos gráficos [1] .

Notas

↑ Fink, Jacobson, Kinch, Roberts, 1985 .

Literatura

CD Godsil, BD McKay. Un nuevo producto gráfico y su espectro // Bull. Austral. Matemáticas. Soc.. - 1978. - T. 18 , núm. 1 . — P. 21–28 . -doi : 10.1017/ S0004972700007760 .
JF Fink, MS Jacobson, LF Kinch, J. Roberts. En gráficos que tienen un número de dominación la mitad de su orden // Punto. Matemáticas. Hungría.. - 1985. - T. 16 , núm. 4 . — S. 287–293 . -doi : 10.1007/ BF01848079 .
KM Koh, DG Rogers, T. Tan. Productos de árboles agraciados // Matemáticas discretas . - 1980. - T. 31 , núm. 3 . — S. 279–292 . - doi : 10.1016/0012-365X(80)90139-9 .