A suitable product of graphs

Has anyone ever seen the following construction in graph theory?

Consider the complete graph on $3$ vertices, say $K_3=K_3(1)$. Now pick a copy of $K_3$ for any vertex of $K_3$, $K_3^{(1)}, K_3^{(2)},K_3^{(3)}$ and arrange them in a triangle. Connect one of the vertices of $K_3^{(i)}$ to one of the vertices of $K_3^{(j)}$ in such a way to obtain the second graph, $K_3(2)$ in the following figure:

Now pick a copy of the resulting graph for any vertex of $K_3$ and repeat the procedure in such a way that one of the vertices having connectivity $2$ in the copy $i$ (they are exactly $3$) is connected to a similar vertex in the copy $j$. You'll obtain a figure similar to the third in the image, let's call it $K_3(3)$, and "in the end" some kind of Sierpinski-like graph will be on your sheet of paper.

My zero-th question is: how can this construction be generalized (if it can)? Fix an integer $p\ge 2$; the complete graph with $p$ vertices allows one to build the same kind of object (a connectivity argumet helps in defining without ambiguity how sides have to be connected in passing to $K_p(n)$ to $K_p(n+1)$ -notation is obvious I think), and objects similar to

My real questions:

1. Is this construction already known/studied/used? Is it useful?
2. Can one take a step futher and generalize this idea defining a suitable "product" between two graphs? The idea is: given $G,H$ graphs define $G\otimes H$ taking a copy of $G$ for any vertex of $H$, and then "connect various copies of $G$ according to the connectivity of $H$" (I'm totally aware that this is far from being well-defined: part of the question is "how can it be properly defined?"). The idea is to obtain somethng like this:

Solution 1:

Here's a way to define $G \otimes H$ when $G = K_p$ and each vertex of $H$ has degree at most $p$. It's one good way to generalize your construction.

The vertex set $V(G \otimes H)$ is $V(G) \times V(H)$. We'll define the edges $E(G \otimes H)$. We consider that each $e \in E$ is a subset of $V$ of size 2.

For $h \in V(H)$, define $E_h(H) = \{e: h \in e\} \subseteq E(H)$. Define $X_h = \{h\} \times E_h \subseteq V(H) \times E(H)$, and $X = \bigcup_h X_h$. By the assumption on degrees in $H$, choose $f: X \rightarrow V(G)$ such that for each every $h$, $f \mid X_h$ is one-to-one.

Now for $\beta \in E(H)$, we can define the corresponding edge in the big graph: $\beta_G = \{(f(h, \beta), h): h \in \beta\}$. We also want a copy of $G$ for each vertex of $H$, which is $\bigcup \{E(G) \times \{h\}: h \in V(H)\}$. So the whole $E(G \otimes H) = (\bigcup_h E(G) \times \{h\}) \cup \{\beta_G\}_\beta$.

The choice of $f$ does not matter, because of the symmetry of each copy of $G$. So this completes the definition.

Solution 2:

I'm the friend @tetrapharmakon was talking about.

I want to give half an answer and state a more specific question.

Consider two graphs $G$ and $H$ of vertices $V(G)$ and $V(H)$. The product $G\otimes H$ we'd like to define

• must contain $|V(G)|$ copies of $V(H)$ as disjoint subgraphs;
• these subgraphs must be connected like the vertices of $G$ in some way.

I thought of a way to make the sense of "like the vertices" precise. To account for the ambiguity of "in some way" I define a family of products instead of a single one.

Given a function $\phi:V(G)\times V(G)\rightarrow V(H)$ let the product $G\otimes_\phi H$ be defined as follows. The vertices are $V(G\otimes_\phi H)=V(G)\times V(H)$. Connect two of them, say $(g,h)$ and $(g',h')$

• either if $g=g'$ with $h$ and $h'$ adjacent in $H$ (this builds the subgraphs)
• or if $h=\phi(g,g')$ and $h'=\phi(g',g)$ (this connects them).

This definition catches the way how we want the subgraphs to be connected and relegates the ambiguity in how to do so to the choice of $\phi$, giving a family of well defined products with the properties we seek.

This may be a starting point to answer question 2. But now I want to apply question 1. to these products I just defined: are they a known/studied/useful structure?

As an example, if $\phi_1:(i,j)\mapsto j$, $\phi_2:(i,j)\mapsto(j,j)$ and $\phi_3:(i,j)\mapsto(j,(j,j))$ then $K_p\otimes_{\phi_1}K_p$, $K_p\otimes_{\phi_2}\left(K_p\otimes_{\phi_1}K_p\right)$ and $K_p\otimes_{\phi_3}\left[K_p\otimes_{\phi_2}\left(K_p\otimes_{\phi_1}K_p\right)\right]$ give the first three iterations of the gaskets we were building at the beginning. The pattern for the following iterations is quite clear.

@tomasz. I may have misunderstood you but what you're describing sounds to me like the lexicographic product of two graphs. The problem is that at the very least we want the product to reproduce the gasket-like structures of the pictures above when multiplying complete graphs. The lexicographical product fails to achieve this. Unfortunately every common graph product I know of (cartesian, tensor, lexicographical, normal, co-normal and rooted) fails to do this.

@DanLitt. The idea seems good but it heavily relies on how we embed the graphs and on the way we measure distances. In my opinion it would be very tricky to formalize it - that is, I don't know how to do it.

@Hew Wolff. I like the way you relied on the symmetry of the first factor to give an unambiguous definition.