The Sierpiński product of graphs

Abstract

In this paper we introduce a product-like operation that generalizes the construction of generalized Sierpiński graphs. Let $G,H$ be graphs and let $f:V(G)\to V(H)$ be a function. Then the Sierpiński 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^{\prime })\}$ is an edge in $K$ for every $g\in V(G)$ and every $\{h,h^{\prime }\}\in E(H)$, -- $\{(g,f(g^{\prime }),(g^{\prime },f(g))\}$ is an edge in $K$ for every edge $\{g,g^{\prime }\}\in E(G)$; and $\phi :V(G)\to V(K)$ is a function that maps every vertex $g\in V(G)$ to the vertex $(g,f(g))\in V(K)$. Graph $K$ will be denoted by $G{\otimes }_{f}H$. Function $\phi$ 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ński graph. Some basic properties of the Sierpiński 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$.