Producto tensorial de grafos

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

el conjunto de vértices de $G \times H$ es el producto cartesiano $V (G) \times V (H)$ ; y
los vértices ( g , h ) y ( g' , h' ) son adyacentes en G × H si y solo si
- $g$ es adyacente a $g'$ en $G$ , y
- $h$ es adyacente a $h'$ en $H$ .

El producto tensorial también se denomina producto directo , producto de Kronecker , producto categórico , producto cardinal , producto relacional , producto directo débil o conjunción . Como operación sobre relaciones binarias, el producto tensorial fue introducido por Alfred North Whitehead y Bertrand Russell en sus Principia Mathematica (1912). También es equivalente al producto de Kronecker de las matrices de adyacencia de los grafos. ^[1]

La notación $G \times H$ también se utiliza (y antiguamente se utilizaba normalmente) para representar otra construcción conocida como producto cartesiano de grafos , pero hoy en día se refiere más comúnmente al producto tensorial. El símbolo de la cruz muestra visualmente las dos aristas resultantes del producto tensorial de dos aristas. ^[2] Este producto no debe confundirse con el producto fuerte de grafos .

Ejemplos

El producto tensorial $G \times K 2$ es un grafo bipartito , llamado doble recubrimiento bipartito de $G$ . El doble recubrimiento bipartito del grafo de Petersen es el grafo de Desargues : $K 2 \times G (5,2) = G (10,3)$ . El doble recubrimiento bipartito de un grafo completo $K n$ es un grafo corona (un grafo bipartito completo $K n, n$ menos un emparejamiento perfecto ).
El producto tensorial de un grafo completo consigo mismo es el complemento de un grafo de Rook . Sus vértices pueden ubicarse en una cuadrícula de $n$ por $n$ , de modo que cada vértice sea adyacente a los vértices que no están en la misma fila o columna de la cuadrícula.

Propiedades

El producto tensorial es el producto de la teoría de categorías en la categoría de grafos y homomorfismos de grafos . Es decir, un homomorfismo con $G \times H$ corresponde a un par de homomorfismos con $G$ y con $H.$ En particular, un grafo $I$ admite un homomorfismo en $G \times H$ si y solo si admite un homomorfismo en $G$ y en $H.$

Para ver que, en una dirección, observe que un par de homomorfismos $f G : I \to G$ y $f H : I \to H$ produce un homomorfismo

{\begin{cases}f:I\to G\times H\\f(v)=\left(f_{G}(v),f_{H}(v)\right)\end{cases}}

En la otra dirección, un homomorfismo $f : I \to G \times H$ puede estar compuesto con los homomorfismos de proyecciones

{\begin{casos}\pi _{G}:G\times H\to G\\\pi _{G}((u,u'))=u\end{casos}}\qquad \qquad {\begin{casos}\pi _{H}:G\times H\to H\\\pi _{H}((u,u'))=u'\end{casos}}

para producir homomorfismos para $G$ y para $H$ .

La matriz de adyacencia de $G \times H$ es el producto Kronecker (tensor) de las matrices de adyacencia de $G$ y $H.$

Si un grafo puede representarse como un producto tensorial, entonces puede haber múltiples representaciones diferentes (los productos tensoriales no satisfacen la factorización única), pero cada representación tiene el mismo número de factores irreducibles. Imrich (1998) ofrece un algoritmo de tiempo polinomial para reconocer grafos de productos tensoriales y encontrar una factorización de dichos grafos.

Si $G$ o $H$ son bipartitos , entonces también lo es su producto tensorial. $G \times H$ es conexo si y solo si ambos factores son conexos y al menos un factor no es bipartito. ^[3] En particular, la doble cubierta bipartita de $G$ es conexa si y solo si $G$ es conexo y no bipartito.

La conjetura de Hedetniemi , que proporcionó una fórmula para el número cromático de un producto tensorial, fue refutada por Yaroslav Shitov (2019).

El producto tensorial de grafos dota a la categoría de grafos y homomorfismos de grafos de la estructura de una categoría monoidal cerrada simétrica . Sea $G$ $0$ el conjunto subyacente de vértices del grafo $G$ . El hom interno $[$ $G$ $,$ $H$ $]$ tiene funciones $f$ $:$ $G$ $0$ $\to$ $H$ $0$ como vértices y una arista desde $f$ $:$ $G$ $0$ $\to$ $H$ $0$ hasta $f'$ $:$ $G$ $0$ $\to$ $H$ $0$ siempre que una arista ${$ $x$ $,$ $y$ $}$ en $G$ implique ${$ $f$ $($ $x$ $),$ $f '$ $($ $y$ $)}$ en $H$ . ^[4]

Véase también

Notas

^ Weichsel 1962.
^ Hahn y Sabidussi 1997.
^ Imrich y Klavžar 2000, teorema 5.29
^ Brown et al. 2008; véase también esta prueba

Referencias

Brown, R.; Morris, I.; Shrimpton, J.; Wensley, CD (2008), "Gráficos de morfismos de grafos", The Electronic Journal of Combinatorics , 15 : A1.
Hahn, Geňa; Sabidussi, Gert (1997), Simetría de grafos: métodos algebraicos y aplicaciones, NATO Advanced Science Institutes Series, vol. 497, Springer, p. 116, ISBN 978-0-7923-4668-5.
Imrich, W. (1998), "Factorización de gráficos de productos cardinales en tiempo polinomial", Discrete Mathematics , 192 : 119–144, doi : 10.1016/S0012-365X(98)00069-7 , MR 1656730
Imrich, Wilfried; Klavžar, Sandi (2000), Gráficos de productos: estructura y reconocimiento , Wiley, ISBN 0-471-37039-8
Shitov, Yaroslav (mayo de 2019), Contraejemplos de la conjetura de Hedetniemi , arXiv : 1905.02167
Weichsel, Paul M. (1962), "El producto Kronecker de grafos", Actas de la American Mathematical Society , 13 (1): 47–52, doi : 10.2307/2033769 , JSTOR 2033769, MR 0133816
Whitehead, AN ; Russell, B. (1912), Principia Mathematica , Cambridge University Press, vol. 2, pág. 384

Enlaces externos

Nicolas Bray. "Producto categórico gráfico". MathWorld .

[FOOTNOTEWeichsel1962-1] Weichsel 1962.

[FOOTNOTEHahnSabidussi1997-2] Hahn y Sabidussi 1997.

[3] Imrich y Klavžar 2000, teorema 5.29

[FOOTNOTEBrownMorrisShrimptonWensley2008-4] Brown et al. 2008; véase también esta prueba