10
$\begingroup$

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:

enter image description here 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 enter image description here

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:

enter image description here

  • 0
    Our hope (I'm turning here a question a friend of mine posed me yesterday) is that at least in the case of $K_p(n)$ different choices lead to isomorphic graphs.2012-09-24
  • 0
    Did somebody remove the comment?2012-09-24
  • 0
    I think that for the construction of $G\otimes H$ to make sense, you need to connect every point in each copy of $H$ with every point in every other copy of $H$ such that there's an edge between the corresponding vertices in $G$. That makes the construction work for arbitrary graphs. It's not much of a generalization. But I doubt you can hope for that, at least not in purely graph-theoretical terms, as it depends on how you embed the graphs in the plane.2012-09-24

2 Answers 2