The Sierpiński product of graphs

Abstract

In this paper we introduce a product-like operation that generalizes the construction of the generalized Sierpiński graphs. Let G, H be graphs and let f: V(G) → V(H) be a function. Then the Sierpiński product of graphs G and H with respect to f, denoted by G ⊗_f H, is defined as the graph on the vertex set V(G) × V(H), consisting of |V(G)| copies of H; for every edge {g, g′} of G there is an edge between copies gH and g′H of form {(g, f(g′), (g′, f(g))}.

Some basic properties of the Sierpiński product are presented. In particular, we show that the graph G ⊗_f H is connected if and only if both graphs G and H are connected and we present some conditions that G, H must fulfill for G ⊗_f H to be planar. As for symmetry properties, we show which automorphisms of G and H extend to automorphisms of G ⊗_f H. In several cases we can also describe the whole automorphism group of the graph G ⊗_f H.

Finally, we show how to extend the Sierpiński product to multiple factors in a natural way. By applying this operation n times to the same graph we obtain an alternative approach to the well-known n-th generalized Sierpiński graph.