ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P1.01 https://doi.org/10.26493/1855-3974.1970.29e (Also available at http://amc-journal.eu) The Sierpiński product of graphs* Jurij Kovič Institute of Mathematics, Physics, and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia, and University of Primorska, FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia Tomaž Pisanski University of Primorska, FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia, and Institute of Mathematics, Physics, and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia Sara Sabrina Zemljič Cambridge Quantum Computing Ltd, 32 St James’s Street, London, SW1A 1HD, United Kingdom Arjana Žitnik † University of Ljubljana, Faculty of Mathematics and Physics, Jadranska 19, 1000 Ljubljana, Slovenia, and Institute of Mathematics, Physics, and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia Dedicated to Professor Wilfried Imrich on the occasion of his 80th birthday. Received 9 October 2019, accepted 30 January 2022, published online 1 September 2022 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 ⊗f H , is defined as the graph on the vertex set V (G) × V (H), consisting of |V (G)| *The authors would like to thank Wilfried Imrich and Primož Šparl for fruitful discussion and Susan Deborah Cook and Luke Morgan for their help in proofreading. They would also like to thank the referees for reading the manuscript carefully and for their detailed comments which helped to improve the presentation of the paper significantly. In particular they would like to thank one referee for pointing out that additional assumptions of connectedness of the graph H in Lemma 2.5(ii) and 2-connectedness of the graph G in Theorem 2.13 and its corollaries are needed. This work was supported in part by ‘Agencija za raziskovalno dejavnost Republike Slovenije’ (Slovenian Research Agency) via Grants P1-0294, J1-9187, J1-7051, J1-7110, J1–1691 and N1–0032 and in part by H2020 Teaming InnoRenew CoE. †Corresponding author. cb This work is licensed under https://creativecommons.org/licenses/by/4.0/ 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 natu- ral 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. Math. Subj. Class. (2020): 05C76, 05C10, 05C40, 20B25 E-mail addresses: jurij.kovic@siol.net (Jurij Kovič), tomaz.pisanski@upr.si (Tomaž Pisanski), sara.zemljic@gmail.com (Sara Sabrina Zemljič), arjana.zitnik@fmf.uni-lj.si (Arjana Žitnik) ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.) ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P1.01 https://doi.org/10.26493/1855-3974.1970.29e (Dostopno tudi na http://amc-journal.eu) Sierpińskijev produkt grafov* Jurij Kovič Inštitut za matematiko, fiziko in mehaniko, Jadranska 19, 1000 Ljubljana, Slovenija, in Univerza na Primorskem, FAMNIT, Glagoljaška 8, 6000 Koper, Slovenija Tomaž Pisanski Univerza na Primorskem, FAMNIT, Glagoljaška 8, 6000 Koper, Slovenija, in Inštitut za matematiko, fiziko in mehaniko, Jadranska 19, 1000 Ljubljana, Slovenija Sara Sabrina Zemljič Cambridge Quantum Computing Ltd, 32 St James’s Street, London, SW1A 1HD, Združeno kraljestvo Arjana Žitnik † Univerza v Ljubljani, Fakulteta za matematiko in fiziko, Jadranska 19, 1000 Ljubljana, Slovenija, in Inštitut za matematiko, fiziko in mehaniko, Jadranska 19, 1000 Ljubljana, Slovenija Posvečeno profesorju Wilfriedu Imrichu ob njegovem 80. rojstnem dnevu. Prejeto 9. oktobra 2019, sprejeto 30. januarja 2022, objavljeno na spletu 1. septembra 2022 Povzetek V tem prispevku vpeljemo operacijo, podobno produktu, ki posplošuje konstrukcijo posplošenih grafov Sierpińskega. Naj bosta G,H grafa in naj bo f : V (G) → V (H) funkcija. Sierpińskijev produkt grafov G in H glede na f , oznaka G⊗f H , je definiran kot graf na množici vozlišč V (G) × V (H), sestavljen iz |V (G)| kopij H; za vsako povezavo {g, g′} grafa G obstaja povezava med kopijama gH in g′H oblike {(g, f(g′), (g′, f(g))}. *Avtorji bi se radi zahvalili Wilfriedu Imrichu in Primožu Šparlu za plodno razpravo, Susan Deborah Cook in Luku Morganu pa za pomoč pri lektoriranju. Prav tako bi se radi zahvalili recenzentom za skrbno branje rokopisa in za njihove podrobne komentarje, ki so pripomogli k bistveno boljši predstavitvi članka. Še posebej bi se radi zahvalili recenzentu, ki je opozoril, da sta potrebne dodatni predpostavki o povezanosti grafa H v lemi 2.5(ii) in o 2-povezanosti grafa G v izreku 2.13 in njegovih posladicah. To delo je delno podprla ‘Agencija za raziskovalno dejavnost Republike Slovenije’ (Slovenian Research Agency) v okviru projektov P1-0294, J1-9187, J1-7051, J1- 7110, J1–1691 in N1–0032 ter delno H2020 Teaming InnoRenew CoE. †Kontaktni avtor. cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/ Predstavljene so nekatere osnovne lastnosti Sierpińskijevega produkta. Pokažemo, da je graf G⊗fH povezan, če in samo če sta oba grafa G in H povezana, in predstavimo pogoje, ki jih morata izpolnjevati G in H , da je graf G ⊗f H ravninski. V zvezi s simetrijskimi lastnostmi pokažemo, kateri avtomorfizmi grafov G in H se dajo razširiti na avtomorfizme G⊗f H . V več primerih lahko opišemo tudi celotno grupo avtomorfizmov grafa G⊗f H . Na koncu pokažemo, kako Sierpińskijev produkt naravno razširimo na več faktorjev. Uporaba te operacije n-krat na istem grafu predstavlja alternativni pristop k dobro znanemu n-temu posplošenemu grafu Sierpińskega. Ključne besede: Grafi Sierpińskega, produkti grafov, povezanost, ravninskost, simetrija. Math. Subj. Class. (2020): 05C76, 05C10, 05C40, 20B25 E-poštni naslovi: jurij.kovic@siol.net (Jurij Kovič), tomaz.pisanski@upr.si (Tomaž Pisanski), sara.zemljic@gmail.com (Sara Sabrina Zemljič), arjana.zitnik@fmf.uni-lj.si (Arjana Žitnik)