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 ⊗fH, 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 ⊗fH 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 ⊗fH to be planar. As for symmetry properties, we show which automorphisms of G and H extend to automorphisms of G ⊗fH. In several cases we can also describe the whole automorphism group of the graph G ⊗fH.
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.
Keywords
Full Text:
MANUSCRIPTDOI: https://doi.org/10.26493/1855-3974.1970.29e
ISSN: 1855-3974
Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications