Producto Cartesiano de Grafos
# Producto Cartesiano de Grafos

En teoría de grafos, el producto cartesiano G$\square$H de los grafos G y H es un grafo tal que

* El conjunto de vértices de G $\square$ H es el producto Cartesiano V(G) × V(H); y
* Dos vértices (u,u' ) y (v,v' ) son adyacentes en G$\square$ H sí y sólo si alguna de las siguientes condiciones se cumple
   * u = v, y u' es adyacente a v' en H, o
   * u' = v' , y u es adyacente a v en G.

El producto Cartesiano de grafos es a veces llamado el producto caja de grafos [Harary 1969].

La operación es associativa, cuando ya que los grafos (F $\square$ G) $\square$ H y F $\square$ (G $\square$ H) son grafos naturalmente isomorfos. La operación es conmutativa como una operación en las clases de isomorfismo de grafos, y más aún, los grafos G $\square$ H y H $\square$ G son naturalmente isomorfos; sin embargo esta no es una operación conmutativa en los grafos etiquetados.

La notación G × H a menudo ha sido utilizado para productos Cartesianos de grafos, pero hoy en día es más generalmente usado para otra construcción, conocida como el producto tensor de grafos. El símbolo cuadrado es una notación intuitiva e inequívoca para el producto Cartesiano, ya que muestra visualmente las cuatro aristas que resultan del producto Cartesiano de dos aristas.[1]

## Ejemplos

* El producto Cartesiano de dos aristas es un ciclo en cuatro vértices: $K_2$ $\square$ $K_2$ = $C_4.$
* El producto Cartesiano de $K_2$ y un grafo de camino es un grafo de escalera.
* El producto Cartesiano de dos grafos de camino es una grafo de celosía.
* El producto Cartesiano de n aristas es un hipercubo:

       $(K_{2})^{\square n}=Q_{n}.$
    Así, el producto Cartesiano de dos grafos de hipercubo es otro hipercubo: $Q_i$ $\square$ $Q_j$ = $Q_{i+j}.$
* El producto Cartesiano de dos grafos medianos es otro grafo mediano.
* El grafo de vértices y aristas de un n-prisma es el grafo producto Cartesiano $K_2$ $\square$ $C_n.$
* El grafo de torre es el producto Cartesiano de dos grafos completos.

## Propiedades

Si un grafo conectado es un producto Cartesiano, entonces este puede ser factorizado únicamente como producto de factores primos, que son grafos que no pueden ser descompuestos como productos de grafos ellos mismos. Sin embargo,Imrich y Klavžar (2000) & Klavžar (2000) describen un grafo no conexo que puede ser expresado en dos maneras diferentes como producto Cartesiano de grafos primos:

    $(K_1$ + $K_2$ + $K_2^2)$ $\square$ $(K_1$ + $K_2^3)$ = $(K_1$ + $K_2^2$ + $K_2^4)$ $\square$ $(K_1$ + $K_2),$

donde el signo de más arriba denota una unión disjunta y los superíndices denotan exponenciación sobre productos Cartesianos.

Un producto Cartesiano es vértice transitivo sí y sólo si cada uno de sus factores lo es.

Un producto Cartesiano es bipartito sí y sólo si cada uno de sus factores lo es. Más generalmente, el número cromático del producto Cartesiano satisface la ecuación

    χ(G $\square$ H) = max {χ(G), χ(H)}.[4]

La conjetura de Hedetniemi satisface una igualdad relacionada para el producto tensor de grafos. El número de independencia de un producto Cartesiano no es tan fácilmente calculado, pero como Vizing (1963) probó, satisface las desigualdades

    α(G)α(H) + min{|V(G)|-α(G) , |V(H)|-α(H)} ≤ α(G H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.$\square$

La conjetura de Vizing declara que el número de dominación de un producto Cartesiano satisface la desigualdad

    γ(G $\square$ H) ≥ γ(G)γ(H).

El producto cartesiano de grafos de distancia unitaria es otro grafo de distancia unitaria.[5]

El producto cartesiano de grafos puede ser reconocido eficientemente, en tiempo lineal.

## Teoría de grafos algebraica

La teoría de grafos algebraica puede utilizarse para analizar el producto Cartesiano de grafos. Si el grafo $G_{1}$ tiene $n_{1}$ vértices y una matriz de $n_{1}\times n_{1}$de adyacencia $\mathbf {A} _{1}$, y el grafo $G_{2}$ tiene $n_{2}$ vértices y una matriz de $n_{2}\times n_{2}$ de adyacencia $\mathbf {A} _{2}$, entonces la matriz de adyacencia del producto Cartesiano de ambos grafos está dado por

    ,$\mathbf {A} _{1\square 2}=\mathbf {A} _{1}\otimes \mathbf {I} _{n_{2}}+\mathbf {I} _{n_{1}}\otimes \mathbf {A} _{2}$,

Dónde $\otimes$ denota el producto Kronecker de matrices e $\mathbf {I} _{n}$ denota la matriz de $n\times n$ que es la identidad.[7] La matriz de adyacencia del producto Cartesiano es por lo tanto la suma de Kronecker de las matrices de adyacencia de los factores.

## Teoría de categorías

Viendo un grafo como una categoría cuyos objetos son los vértices y cuyos morfismos son los caminos en el grafo, el producto Cartesiano de grafos corresponde al producto de tensor gracioso de categorías. El producto Cartesiano de grafos es uno de los dos productos de grafos que convierten a la categoría de grafos y homomorfismos de grafo en una categoría simétrica cerrada monoidal (en contraste con simplemente monoidal simétrica), el otro tal producto siendo el producto de tensor de grafos.[8] El hom$[G,H]$ interno para el producto Cartesiano de grafos tiene homomorfismos de grafo de $G$ a $H$ como vértices y "transformaciones antinaturales" entre ellos como aristas.

## Historia

Según Imrich y Klavžar (2000), los productos Cartesianos de grafos fueron definidos en 1912 por Whitehead y Russell. Estos fueron repetidamente redescubiertos más tarde, notablemente por Gert Sabidussi (1960).

