Un producto adecuado de los gráficos

Question

Alguien ha visto alguna vez las siguientes construcción de la teoría de grafos?

Considere el grafo completo en $3$ vértices, decir $K_3=K_3(1)$. Ahora coger una copia de $K_3$ para cualquier vértice de $K_3$, $K_3^{(1)}, K_3^{(2)},K_3^{(3)}$ y organizarlos en un triángulo. Conecte uno de los vértices de $K_3^{(i)}$ a uno de los vértices de $K_3^{(j)}$ de tal manera de obtener el segundo gráfico, $K_3(2)$ en la siguiente figura:

Ahora recoger una copia de la gráfica resultante para cualquier vértice de $K_3$ y repita el procedimiento de tal manera que uno de los vértices de tener conectividad $2$ en la copia de $i$ (son exactamente $3$) está conectado a una similar vértice en la copia de $j$. Usted obtendrá una figura similar a la tercera en la imagen, vamos a llamar a $K_3(3)$, y "al final" algún tipo de Sierpinski-como gráfico en la hoja de papel.

Mi zero-th pregunta es: ¿cómo puede esta construcción se generaliza (si se puede)? Fijar un número entero $p\ge 2$; el grafo completo con $p$ vértices permite construir el mismo tipo de objeto (una conectividad argumet ayuda a definir sin ambigüedad cómo las partes tienen que estar conectados en el paso de a $K_p(n)$ $K_p(n+1)$- notación es obvio, creo), y objetos similares para

Mi pregunta:

1. Es de esta construcción ya conocido, estudiado/usa? Es útil?
2. Se puede dar un paso más y generalizar esta idea de la definición de un adecuado "producto" entre los dos gráficos? La idea es: dado $G,H$ gráficos definir $G\otimes H$ tomar una copia de $G$ para cualquier vértice de $H$, y luego "conectar varias copias de $G$ de acuerdo a la conectividad de $H$" (soy totalmente consciente de que esto está lejos de ser bien definidas: la primera parte de la pregunta es "¿cómo puede ser definido correctamente?"). La idea es obtener somethng como este:

Answer 1

He aquí una manera de definir $G \otimes H$ al $G = K_p$ y cada vértice de $H$ tiene un grado en la mayoría de las $p$. Es una buena manera de generalizar su construcción.

El conjunto de vértices $V(G \otimes H)$$V(G) \times V(H)$. Vamos a definir los bordes $E(G \otimes H)$. Consideramos que cada una de las $e \in E$ es un subconjunto de a $V$ de tamaño 2.

Para $h \in V(H)$, definir $E_h(H) = \{e: h \in e\} \subseteq E(H)$. Definir $X_h = \{h\} \times E_h \subseteq V(H) \times E(H)$, e $X = \bigcup_h X_h$. Por la asunción grados en $H$, elija $f: X \rightarrow V(G)$ tal que para cada $h$, $f \mid X_h$ es uno-a-uno.

Ahora para $\beta \in E(H)$, podemos definir el borde correspondiente en el gráfico grande: $\beta_G = \{(f(h, \beta), h): h \in \beta\}$. También queremos una copia de $G$ por cada vértice de $H$,$\bigcup \{E(G) \times \{h\}: h \in V(H)\}$. Así, toda la $E(G \otimes H) = (\bigcup_h E(G) \times \{h\}) \cup \{\beta_G\}_\beta$.

La elección de $f$ no importa, debido a la simetría de cada copia de $G$. Así que este completa la definición.

Answer 2

Yo soy el amigo @tetrapharmakon estaba hablando.

Quiero dar la mitad de una respuesta y una más pregunta específica.

Considere dos gráficos de $G$ $H$ de vértices $V(G)$$V(H)$. El producto $G\otimes H$ nos gustaría definir

• debe contener $|V(G)|$ copias de $V(H)$ como discontinuo subdiagramas;
• estos subdiagramas debe estar conectado como los vértices de $G$ en alguna manera.

Pensé en una manera de hacer que el sentido de "como los vértices" precisa. Para dar cuenta de la ambigüedad de la "de alguna manera" me definen una familia de productos en lugar de uno solo.

Dada una función de $\phi:V(G)\times V(G)\rightarrow V(H)$ deje que el producto se $G\otimes_\phi H$ se define de la siguiente manera. Los vértices se $V(G\otimes_\phi H)=V(G)\times V(H)$. Conectar dos de ellos, decir $(g,h)$ $(g',h')$

• ya sea si $g=g'$ $h$ $h'$ adyacente en $H$ (esto genera la subdiagramas)
• o si $h=\phi(g,g')$ $h'=\phi(g',g)$ (este se conecta a ellos).

Esta definición de las capturas de la forma en cómo queremos que sean los subdiagramas para ser conectado y relega a la ambigüedad en el modo de hacerlo para la elección de $\phi$, dando una familia de productos con las propiedades que buscamos.

Esto puede ser un punto de partida para responder a la pregunta 2. Pero ahora quiero solicitar la pregunta 1. a estos productos me acaba de definir: son un conocido, estudiado/útil de la estructura?

Como un ejemplo, si $\phi_1:(i,j)\mapsto j$, $\phi_2:(i,j)\mapsto(j,j)$ y $\phi_3:(i,j)\mapsto(j,(j,j))$ $K_p\otimes_{\phi_1}K_p$, $K_p\otimes_{\phi_2}\left(K_p\otimes_{\phi_1}K_p\right)$ y $K_p\otimes_{\phi_3}\left[K_p\otimes_{\phi_2}\left(K_p\otimes_{\phi_1}K_p\right)\right]$ dar las tres primeras iteraciones de las juntas estábamos construyendo en el principio. El patrón para las siguientes iteraciones es muy clara.

@tomasz. Yo haya entendido mal, pero lo que describes me suena a la lexicográfica del producto de dos gráficos. El problema es que, al menos, queremos que el producto a reproducir la junta-como las estructuras de las fotos de arriba cuando se multiplica completa de los gráficos. La lexicográfica producto falla para lograr esto. Por desgracia todos los comunes gráfico de producto conozco (cartesiano, tensor, lexicográfica, normal, co-normal y arraigada) no lo hace.

@DanLitt. La idea parece buena, pero depende en gran medida de cómo nos incrustar los gráficos y en la manera que tenemos de medir distancias. En mi opinión sería muy difícil de formalizar, es decir, no sé cómo hacerlo.

@Hew Wolff. Me gusta la forma en que se basó en la simetría del primer factor para dar una clara definición.