The Sierpiński product of graphs

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

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 GfH, 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 GfH is connected if and only if both graphs G and H are connected and we present some conditions that G, H must fulfill for GfH to be planar. As for symmetry properties, we show which automorphisms of G and H extend to automorphisms of GfH. In several cases we can also describe the whole automorphism group of the graph GfH.

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


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

Full Text:

MANUSCRIPT


DOI: 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