2019/04/08 by Kovič, Jurij, Pisanski, Tomaž, Zemljič, Sara Sabrina +1
#05C10 #05C12 #05C76 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1904.04180
In this paper we introduce a product-like operation that generalizes the construction of 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 G and H with respect to f is defined as a pair (K,φ), where K is a graph on the vertex set V(G) × V(H) with two types of edges: -- \(g,h),(g,h')\ is an edge in K for every g∈ V(G) and every \h,h'\∈ E(H), -- \(g,f(g'),(g',f(g))\ is an edge in K for every edge \g,g'\ ∈ E(G); and φ: V(G) → V(K) is a function that maps every vertex g ∈ V(G) to the vertex (g,f(g)) ∈ V(K). Graph K will be denoted by G⊗f H. Function φ is needed to define the product of more than two factors. By applying this operation n times to the same graph we obtain the n-th generalized Sierpiński graph. Some basic properties of the Sierpiński product are presented. In particular, we show that G ⊗f H is connected if and only if both G and H are connected and we present some necessary and sufficient conditions that G,H must fulfill in order 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 many cases we can also describe the whole automorphism group of G⊗f H.