Producto Cartesiano de Grafos

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

• El conjunto de vértices de G ${\displaystyle \square }$ H es el producto Cartesiano V(G) × V(H); y
• Dos vértices (u,u' ) y (v,v' ) son adyacentes en G${\displaystyle \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 asociativa, cuando ya que los grafos (F ${\displaystyle \square }$ G) ${\displaystyle \square }$ H y F ${\displaystyle \square }$ (G ${\displaystyle \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 ${\displaystyle \square }$ H y H ${\displaystyle \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]

• El producto Cartesiano de dos aristas es un ciclo en cuatro vértices: K₂ ${\displaystyle \square }$ K₂ = C₄.
• El producto Cartesiano de K₂ 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:

${\displaystyle (K_{2})^{\square n}=Q_{n}.}$

Así, el producto Cartesiano de dos grafos de hipercubo es otro hipercubo: Q_i ${\displaystyle \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₂ ${\displaystyle \square }$ C_n.
• El grafo de torre es el producto Cartesiano de dos grafos completos.

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.^[1]​ 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₁ + K₂ + K₂²) ${\displaystyle \square }$ (K₁ + K₂³) = (K₁ + K₂² + K₂⁴) ${\displaystyle \square }$ (K₁ + K₂),

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.^[2]​

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 ${\displaystyle \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)|}.${\displaystyle \square }$

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

γ(G ${\displaystyle \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.^[3]​

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

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

Dónde ${\displaystyle \otimes }$ denota el producto Kronecker de matrices e ${\displaystyle \mathbf {I} _{n}}$ denota la matriz de ${\displaystyle 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.

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${\displaystyle [G,H]}$ interno para el producto Cartesiano de grafos tiene homomorfismos de grafo de ${\displaystyle G}$ a ${\displaystyle H}$ como vértices y "transformaciones antinaturales" entre ellos como aristas.^[4]​

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

• Aurenhammer, F.; Hagauer, J.; Imrich, W. (1992), «Cartesian graph factorization at logarithmic cost per edge», Computational Complexity 2 (4): 331-349, doi:10.1007/BF01200428 ..
• Feigenbaum, Joan; Hershberger, John; Schäffer, Alejandro A. (1985), «A polynomial time algorithm for finding the prime factors of Cartesian-product graphs», Discrete Applied Mathematics 12 (2): 123-138, doi:10.1016/0166-218X(85)90066-6 ..
• Hahn, Geňa; Sabidussi, Gert (1997), Graph symmetry: algebraic methods and applications, NATO Advanced Science Institutes Series 497, Springer, p. 116, ISBN 978-0-7923-4668-5 ..
• Horvat, Boris; Pisanski, Tomaž (2010), «Products of unit distance graphs», Discrete Mathematics 310 (12): 1783-1792, doi:10.1016/j.disc.2009.11.035 ..
• Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8 ..
• Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Graphs and their Cartesian Products, A. K. Peters, ISBN 1-56881-429-1 ..
• Imrich, Wilfried; Peterin, Iztok (2007), «Recognizing Cartesian products in linear time», Discrete Mathematics 307 (3-5): 472-483, doi:10.1016/j.disc.2005.09.038 ..
• Kaveh, A.; Rahami, H. (2005), «A unified method for eigendecomposition of graph products», Communications in Numerical Methods in Engineering with Biomedical Applications 21 (7): 377-388, doi:10.1002/cnm.753 ..
• Sabidussi, G. (1957), «Graphs with given group and given graph-theoretical properties», Canadian Journal of Mathematics 9: 515-525, doi:10.4153/CJM-1957-060-7 ..
• Sabidussi, G. (1960), «Graph multiplication», Mathematische Zeitschrift 72: 446-457, doi:10.1007/BF01162967 ..
• Vizing, V. G. (1963), «The Cartesian product of graphs», Vycisl. Sistemy 9: 30-43 ..
• Weber, Mark (2013), «Free products of higher operad algebras», TAC 28 (2): 24-65 ..

• Weisstein, Eric W. «Graph Cartesian Product». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.