En teoría matemática de grafos , el producto con raíz de un gráfico G y un gráfico con raíz H se define de la siguiente manera: tome | V ( G ) | copias de H , y para cada vérticede G , identificarcon el nodo raíz de la i -ésima copia de H .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/8/82/Graph-rooted-product.svg/300px-Graph-rooted-product.svg.png)
Más formalmente, asumiendo que V ( G ) = { g 1 , ..., g n }, V ( H ) = { h 1 , ..., h m } y que el nodo raíz de H es, definir
dónde
y
Si G también está enraizado en g 1 , se puede ver el producto en sí como enraizado en ( g 1 , h 1 ). El producto enraizado es un subgrafo del producto cartesiano de los mismos dos gráficos.
Aplicaciones
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) utilizó productos enraizados para encontrar elegantes numeraciones para una amplia familia de árboles.
Si H es un gráfico completo de dos vértices K 2 , entonces para cualquier gráfico G , el producto con raíz de G y H tiene un número de dominio exactamente la mitad de su número de vértices. Todo gráfico conectado 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 gráfico de ciclo de cuatro vértices . Estos gráficos pueden usarse para generar ejemplos en los que el límite de la conjetura de Vizing , una desigualdad no probada entre el número de dominación de los gráficos en un producto gráfico diferente, el producto cartesiano de los gráficos , se cumple exactamente ( Fink et al. 1985 ). También son gráficos bien cubiertos .
Referencias
- Godsil, CD ; McKay, BD (1978), "Un nuevo producto gráfico y su espectro" (PDF) , Bull. Austral. Matemáticas. Soc. , 18 (1): 21-28, doi : 10.1017 / S0004972700007760 , MR 0494910.
- Fink, JF; Jacobson, MS; Kinch, LF; Roberts, J. (1985), "Sobre gráficos que tienen un número de dominación la mitad de su orden", Period. Matemáticas. Hungar. , 16 (4): 287–293, doi : 10.1007 / BF01848079 , MR 0833264.
- Koh, KM; Rogers, DG; Tan, T. (1980), "Productos de árboles agraciados", Matemáticas discretas , 31 (3): 279-292, doi : 10.1016 / 0012-365X (80) 90139-9 , MR 0584121.