The Sierpiński product of graphs

Jurij Kovič ; Tomaž Pisanski ; Sara Sabrina Zemljič ; Arjana Žitnik

Ars Mathematica Contemporanea, Tome 23 (2023) no. 1, article no. 01, 25 p.

Résumé

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.

Détail

DOI : 10.26493/1855-3974.1970.29e

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