Productos de grafos generalizados en vista de los grafos de vértice transitivo

Question

El Producto cartesiano de dos gráficos de vértices transitivos es transitivo de vértice.

El grafo de Petersen es transitivo por vértices pero no es el producto cartesiano de dos grafos transitivos por vértices. Pero casi.

El producto cartesiano $G \square H$ de dos gráficos $G, H$ se define por:

• $V(G \square H) = V(G) \times V(H)$
• $(gh)(g'h') \in E(G \square H)$ si $g = g'$ y $hh'\in E(H)$ o $h = h'$ y $gg' \in E(G)$

Con la distancia topológica $d: V \times V \rightarrow \lbrace 0, 1, 2\dots\rbrace \cup \lbrace \infty \rbrace$ la segunda condición dice:

• $(gh)(g'h') \in E(G \square H)$ si $g = g'$ y $d(hh') = 1$ o $h = h'$ y $d(gg') = \mathbf{1}$

Ejemplo: $C_5 \square K_2$

(fuente)

Considere la siguiente generalización $G \square_f H$ con respecto a un etiquetado $f: V(H) \rightarrow \lbrace 1,2,\dots\rbrace$ . (Supongamos que $G$ está conectado y $f(v) \leq \text{diam}(G)$ .)

• $V(G \square_f H) = V(G) \times V(H)$
• $(gh)(g'h') \in E(G \square_f H)$ si $g = g'$ y $d(hh') = 1$ o $h = h'$ y $d(gg') = \mathbf{f(h)}$

Con $f_P(1) = 1, f_P(2) = 2$ encontramos, que el gráfico de Petersen es $C_5 \square_{f_P} K_2$ :

(fuente)

Para los productos cartesianos, es decir $f(v) \equiv 1 $ se mantiene:

• $G\square H$ es transitivo de vértices para todos los grafos transitivos de vértices $G,H$ .
• Existen grafos no triviales de vértice transitivo $F$ sin gráficos de vértices transitivos $G,H$ tal que $F = G\square H$ Por ejemplo, el gráfico de Petersen.

Con "trivial" me refiero a un gráfico completo, un gráfico circular, un producto de gráficos triviales o el complemento de un gráfico trivial.

Quiero hacer las siguientes preguntas:

• Es $G\square_f H$ para todos los grafos con vértices transitivos $G,H$ y $H$ -líneas de señalización $f$ ?

• ¿Existe un grafo no trivial de vértice transitivo $F$ sin gráficos de vértices transitivos $G,H$ y $H$ -etiquetado $f$ tal que $F = G\square_f H$ ?

Porque los gráficos arbitrarios (casi) siempre guardan una sorpresa al aumentar de tamaño mejor debería pedir el ejemplos más pequeños de

• dos gráficos de vértices transitivos $G,H$ y un $H$ -etiquetado $f$ tal que $G\square_f H$ no es vértice-transitivo

• un gráfico no trivial de vértices transitivos $F$ sin gráficos de vértices transitivos $G,H$ y $H$ -etiquetado $f$ tal que $F = > G\square_f H$

Si -hipotéticamente- no hubiera tales ejemplos, esto implicaría que todo grafo de vértice-transitivo es trivial (en el sentido anterior) o un producto (generalizado) de dos grafos de vértice-transitivo. Esto permitiría construir todos los grafos de vértices transitivos a partir de un conjunto base trivial.

Si hay son En estos ejemplos hay dos vías de investigación: tratarlos como casos excepcionales (como los triviales) o profundizar o generalizar la definición de producto.

Answer 1

Para la segunda pregunta, el ejemplo de Will va al grano. Otra descripción: empezar con un $k$ -gon ( $k \gt 3$ un primo impar) y decidir que el grupo cíclico obvio actuará transitivamente en el gráfico final. Las aristas elegidas son una de las $\frac{k-1}2$ órbitas de aristas posibles. Elige algunas órbitas más. Como $k$ es primo, no es posible ningún producto.

Un contraejemplo tonto a la primera pregunta es imitar la construcción del gráfico de Peterson con un $4$ ciclo. Con $f_P(1) = 1, f_P(2) = 2$ encontramos, que $C_4 \square_{f_P} K_2$ tiene cuatro vértices de grado $3$ y cuatro de grado $2$ .

Un ejemplo regular pero no transitivo es $C_9 \square_{f_P} K_2$ con $f_P(1) = 1, f_P(2) = 3.$ Ahora todos los vértices son de grado $3$ pero la mitad están en triángulos y la otra mitad no.

más tarde Dudo que esto sea una construcción útil. Es fácil hacer un grafo bipartito de vértices transitivos de orden $2p$ con $p$ un primo impar. Ninguno de ellos podría ser un producto. Un producto $A \square_f B$ con $2p$ vértices o bien tiene $A=K_2$ en cuyo caso es un producto cartesiano y no bipartito, o $B=K_2$ en cuyo caso se trata de dos vértices transitivos no triviales $p$ gráficos de vértices unidos por un solo emparejamiento y, de nuevo, no podían ser bipartitos.

Considere las familias como $K_{2m}$ menos una coincidencia o $K_{m,m}$ o $K_{m,m}$ menos una coincidencia. ¿Puedes construir todos estos o incluso alguno de estos para $m \gt 5$ (No sé si $m=3,4,5$ pero imagino que podría haber algunos casos pequeños).