The Sierpiński product of graphs
DOI:
https://doi.org/10.26493/1855-3974.1970.29eKeywords:
Sierpiński graphs, graph products, connectivity, planarity, symmetryAbstract
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.
Downloads
Published
Issue
Section
License
Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/