The Sierpiński product of graphs




Sierpiński graphs, graph products, connectivity, planarity, symmetry


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 Gf 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 gH 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 Gf 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 Gf H to be planar. As for symmetry properties, we show which automorphisms of G and H extend to automorphisms of Gf H. In several cases we can also describe the whole automorphism group of the graph Gf 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.