The Sierpi\'nski product of graphs

In this paper we introduce a product-like operation that generalizes the construction of generalized Sierpi'nski graphs. Let $G,H$ be graphs and let $f:V(G)\to V(H)$ be a function. Then the Sierpi'nski product of $G$ and $H$ with respect to $f$ is defined as a pair $(K,\phi )$, where $K$ is a graph on the vertex set $V(G)\times V(H)$ with two types of edges: – $\{(g,h),(g,h^{\mathrm{\prime }})\}$ is an edge in $K$ for every $g\in V(G)$ and every $\{h,h^{\mathrm{\prime }}\}\in E(H)$, – $\{(g,f(g^{\mathrm{\prime }}),(g^{\mathrm{\prime }},f(g))\}$ is an edge in $K$ for every edge ${g,g’} \in E(G)$;and$\varphi: V(G) \to V(K)$isafunctionthatmapseveryvertex$g \in V(G)$tothevertex$(g,f(g)) \in V(K)$\mathrm{.}Graph$K$willbedenotedby$G\otimes_f H$\mathrm{.}Function$\varphi$ is needed to define the product of more than two factors. By applying this operation $n$ times to the same graph we obtain the $n$-th generalized Sierpi'nski graph. Some basic properties of the Sierpi'nski product are presented. In particular, we show that $G{\otimes }_{f}H$ is connected if and only if both $G$ and $H$ are connected and we present some necessary and sufficient conditions that $G,H$ must fulfill in order for $G{\otimes }_{f}H$ to be planar. As for symmetry properties, we show which automorphisms of $G$ and $H$ extend to automorphisms of $G{\otimes }_{f}H$. In many cases we can also describe the whole automorphism group of $G{\otimes }_{f}H$.