Producto cartesiano de gráficas

En teoría de grafos , el producto cartesiano G □ H de los grafos G y H es un grafo tal que:

• el conjunto de vértices de G □ H es el producto cartesiano V ( G ) × V ( H ) ; y
• Dos vértices ( u , v ) y ( u' , v' ) son adyacentes en G □ H si y solo si se cumple alguna de las siguientes condiciones :
  • u = u' y v es adyacente a v' en H , o
  • v = v' y u esadyacente a u' en G.

El producto cartesiano de grafos a veces se denomina producto de cajas de grafos. ^{[ 1 ]}

La operación es asociativa , ya que los grafos ( F □ G ) □ H y F □ ( G □ H ) son isomorfos de forma natural . La operación es conmutativa como operación sobre clases de isomorfismo de grafos, y más aún, los grafos G □ H y H □ G son isomorfos de forma natural , pero no es conmutativa como operación sobre grafos con etiquetas en los vértices .

La notación G × H se ha utilizado con frecuencia para productos cartesianos de grafos, pero actualmente se usa más comúnmente para otra construcción conocida como producto tensorial de grafos . El símbolo cuadrado pretende ser una notación intuitiva e inequívoca para el producto cartesiano, ya que muestra visualmente las cuatro aristas resultantes del producto cartesiano de dos aristas. ^{[ 2 ]}

• El producto cartesiano de dos aristas es un ciclo de cuatro vértices: K ₂ □ K ₂ = C ₄ .
• El producto cartesiano de K ₂ y un grafo de caminos es un grafo de escalera .
• El producto cartesiano de dos grafos de caminos es un grafo de cuadrícula .
• El producto cartesiano de n aristas es un hipercubo:

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

Por lo tanto, el producto cartesiano de dos grafos hipercubo es otro hipercubo: Q _i □ Q _j = Q _i+j .

• El producto cartesiano de dos gráficas medianas es otra gráfica mediana.
• El grafo de vértices y aristas de un prisma n es el grafo de producto cartesiano K ₂ □ C _n .
• El grafo de la torre es el producto cartesiano de dos grafos completos.

Si un grafo conexo es un producto cartesiano, puede factorizarse de forma única como un producto de factores primos, grafos que no pueden descomponerse a su vez como productos de grafos. ^{[ 3 ]} Sin embargo, Imrich y Klavžar (2000) describen un grafo desconectado que puede expresarse de dos maneras diferentes como un producto cartesiano de grafos primos:

${\displaystyle (K_{1}+K_{2}+K_{2}^{2})\mathbin {\square } (K_{1}+K_{2}^{3})=(K_{1}+K_{2}^{2}+K_{2}^{4})\mathbin {\square } (K_{1}+K_{2}),}$

donde el signo más denota la unión disjunta y los superíndices denotan la exponenciación sobre productos cartesianos. Esto está relacionado con la identidad que

${\displaystyle {\begin{aligned}(1+x+x^{2})(1+x^{3})&=(1+x^{2}+x^{4})(1+x)\\&=1+x+x^{2}+x^{3}+x^{4}+x^{5}\\&=(1+x)(1+x+x^{2})(1-x+x^{2})\end{aligned}}}$

Ambos factores${\displaystyle 1+x^{3}}$y${\displaystyle 1+x^{2}+x^{4}}$No son polinomios irreducibles , pero sus factores incluyen coeficientes negativos y, por lo tanto, los grafos correspondientes no pueden descomponerse. En este sentido, la falta de factorización única en grafos (posiblemente desconectados) es similar a afirmar que los polinomios con coeficientes enteros no negativos forman un semianillo que no cumple la propiedad de factorización única .

Un producto cartesiano es transitivo por vértices si y solo si cada uno de sus factores lo es. ^{[ 4 ]}

Un producto cartesiano es bipartito si y solo si cada uno de sus factores lo es. De manera más general, el número cromático del producto cartesiano satisface la ecuación

${\displaystyle \chi (G\mathbin {\square } H)=\max\{\chi (G),\chi (H)\}.}$^{[ 5 ]}

La conjetura de Hedetniemi establece una igualdad relacionada para el producto tensorial de grafos . El número de independencia de un producto cartesiano no se calcula tan fácilmente, pero como demostró Vizing (1963) satisface las desigualdades.

${\displaystyle \alpha (G)\alpha (H)+\min\{|V(G)|-\alpha (G),|V(H)|-\alpha (H)\}\leq \alpha (G\mathbin {\square } H)\leq \min\{\alpha (G)|V(H)|,\alpha (H)|V(G)|\}.}$

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

${\displaystyle \gamma (G\mathbin {\square } H)\geq \gamma (G)\gamma (H).}$

El producto cartesiano de grafos de distancia unitaria es otro grafo de distancia unitaria. ^{[ 6 ]}

Los grafos de producto cartesiano se pueden reconocer de manera eficiente, en tiempo lineal . ^{[ 7 ]}

El número de aristas | E ( G □ H )| es igual a | V ( G )|| E ( H )| + | V ( H )|| E ( G )| .

La teoría algebraica de grafos se puede utilizar para analizar el producto cartesiano de grafos. Si el grafo${\displaystyle G_{1}}$tiene${\displaystyle n_{1}}$vértices y el${\displaystyle n_{1}\times n_{1}}$matriz de adyacencia${\displaystyle \mathbf {A} _{1}}$y el gráfico${\displaystyle G_{2}}$tiene${\displaystyle n_{2}}$vértices y el${\displaystyle n_{2}\times n_{2}}$matriz de adyacencia${\displaystyle \mathbf {A} _{2}}$, entonces la matriz de adyacencia del producto cartesiano de ambos grafos viene dada por

${\displaystyle \mathbf {A} _{1\mathbin {\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 de Kronecker de matrices y${\displaystyle \mathbf {I} _ {n}}$denota el${\displaystyle n\times n}$matriz identidad . ^{[ 8 ]} La matriz de adyacencia del producto cartesiano de grafos es, por lo tanto, la suma de Kronecker de las matrices de adyacencia de los factores.

Considerando un grafo como una categoría cuyos objetos son los vértices y cuyos morfismos son los caminos del grafo, el producto cartesiano de grafos corresponde al peculiar producto tensorial de categorías. El producto cartesiano de grafos es uno de los dos productos de grafos que transforman la categoría de grafos y homomorfismos de grafos en una categoría monoidal cerrada simétrica (a diferencia de una meramente monoidal simétrica), siendo el otro el producto tensorial de grafos . ^{[ 9 ]} El homomorfismo interno${\displaystyle [G,H]}$para el producto cartesiano de grafos tiene homomorfismos de grafos de${\displaystyle G}$a${\displaystyle H}$como vértices y " transformaciones antinaturales " entre ellos como aristas. ^{[ 9 ]}

Según Imrich y Klavžar (2000) , los productos cartesianos de grafos fueron definidos en 1912 por Whitehead y Russell . Posteriormente fueron redescubiertos repetidamente, en particular por Gert Sabidussi ( 1960 ) . 

• Aurenhammer, F .; Hagauer, J.; Imrich, W. (1992), "Factorización de grafos cartesianos con coste logarítmico por arista", Computational Complexity , 2 (4): 331–349 , doi : 10.1007/BF01200428 , MR 1215316 .
• Feigenbaum, Joan ; Hershberger, John ; Schäffer, Alejandro A. (1985), "Un algoritmo de tiempo polinomial para encontrar los factores primos de grafos de producto cartesiano", Discrete Applied Mathematics , 12 (2): 123–138 , doi : 10.1016/0166-218X(85)90066-6 , MR 0808453 .
• Hahn, Geňa; Tardif, Claude (1997), "Homomorfismos de grafos: estructura y simetría" , en Hahn, Geňa; Sabidussi, Gert (eds.), Simetría de grafos: métodos algebraicos y aplicaciones , NATO Advanced Science Institutes Series C: Ciencias matemáticas y físicas, vol.  497, Kluwer Academic Publishers, p.  116, ISBN 978-0-7923-4668-5.
• Harary, Frank (1969), Teoría de grafos , Addison-Wesley, MR 0256911 , OL 5687805M  .
• Horvat, Boris; Pisanski, Tomaž (2010), "Productos de grafos de distancia unitaria", Matemáticas Discretas , 310 (12): 1783– 1792, doi : 10.1016/j.disc.2009.11.035 , MR 2610282 .
• 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), Gráficos y sus productos cartesianos , AK Peters, ISBN 1-56881-429-1.
• Imrich, Wilfried ; Peterin, Iztok (2007), "Reconocimiento de productos cartesianos en tiempo lineal", Matemáticas Discretas , 307 ( 3–5 ): 472–483 , doi : 10.1016/j.disc.2005.09.038 , MR 2287488 .
• Kaveh, A.; Rahami, H. (2005), "Un método unificado para la descomposición en valores propios de productos de grafos", Communications in Numerical Methods in Engineering with Biomedical Applications , 21 (7): 377–388 , doi : 10.1002/cnm.753 , MR 2151527 .
• Sabidussi, G. (1957), "Grafos con grupo dado y propiedades de teoría de grafos dadas", Canadian Journal of Mathematics , 9 : 515–525 , doi : 10.4153/CJM-1957-060-7 , MR 0094810 .
• Sabidussi, G. (1960), "Multiplicación de gráficos", Mathematische Zeitschrift , 72 : 446– 457, doi : 10.1007/BF01162967 , hdl : 10338.dmlcz/102459 , MR 0209177 .
• Vizing, VG (1963), "El producto cartesiano de grafos", Vycisl. Sistemy , 9 : 30–43 , MR 0209178 .
• Weber, Mark (2013), "Productos libres de álgebras de operadas superiores", Theory and Applications of Categories , 28 (2): 24–65.

• Weisstein, Eric W. "Producto cartesiano de grafos" . MathWorld .