The Sierpiński product of graphs

Authors

DOI:

https://doi.org/10.26493/1855-3974.1970.29e

Keywords:

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

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 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.

Published

2022-09-01

Issue

Section

Articles