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/
2 Ars Math. Contemp. 23 (2023) #P1.01
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
1 Introduction
The motivation for this paper is the study of Sierpiński graphs and their generalizations.
Although the body of this work is essentially self contained, a few remarks about the role
of Sierpiński graphs seem to be appropriate. The family of Sierpiński graphs Snp was
first introduced by Klavžar and Milutinović in [16] as a variant of the Tower of Hanoi
problem. The Sierpiński graphs can be defined recursively as follows: S1p is isomorphic
to the complete graph Kp and Sn+1p is constructed from p copies of S
n
p by adding exactly
one edge between every pair of copies of Sn+1p in a well-defined manner. The Sierpiński
graphs S13 , S
2
3 , and S
3
3 are depicted in Figure 1. In the “classical” case, when p = 3, the
Sierpiński graphs are isomorphic to the Hanoi graphs. More about Sierpiński graphs and
their connections to the Hanoi graphs can be found in the recent second edition of the book
about the Tower of Hanoi puzzle by Hinz et al. [10].
Sierpiński graphs have been extensively studied in most graph-theoretical aspects as
well as in other areas of mathematics and even psychology. Some notable papers are
[11, 13, 15, 17, 18, 22, 26, 27]. An extensive summary of topics studied on and around
Sierpiński graphs is available in the survey paper by Hinz, Klavžar and Zemljič [12]. In
that paper the authors introduced Sierpiński-type graphs as graphs that are derived from or
lead to the Sierpiński triangle fractal.
These families of graphs have been generalized by Gravier, Kovše and Parreau to a
family called generalized Sierpiński graphs [8]. Instead of the complete graph, an arbi-
trary graph G is used as a base graph to form a self-similar graph in the same way as the
Sierpiński graphs are derived from the complete graph: the generalized Sierpiński graph
S1G is isomorphic to the graph G. To construct the n-th iteration generalized Sierpiński
graph SnG for n > 1, take |V (G)| copies of S
n−1
G and add to the labels of vertices in copy x
of Sn−1G the letter x at the beginning. Then, for any edge {x, y} of G, add an edge between
the vertex xy . . . y and the vertex yx . . . x. See Figure 2 for an example of the second iter-
ation generalized Sierpiński graph, where the base graph is the house graph, i.e. the cycle
on five vertices with a chord.
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)
J. Kovič et al.: The Sierpiński product of graphs 3
Figure 1: The Sierpiński graphs S13 , S
2
3 , and S
3
3 .
4
5
1 2
3
44
45
41 42
43
54
55
51 52
53
14
15
11 12
13
24
25
21 22
23
34
35
31 32
33
Figure 2: The generalized Sierpiński graphs S1G and S
2
G when G is the house graph.
4 Ars Math. Contemp. 23 (2023) #P1.01
The generalized Sierpiński graphs have been extensively studied in the past few years
on topics including chromatic number, Randić index, vertex cover number, clique number,
domination number and metric properties; see, for example, [5, 7, 24, 25].
At this point we would like to mention another approach towards the Sierpiński graphs.
The graphs Sn3 appear naturally as subgraphs of repeated truncations of cubic graphs. More
generally, by applying truncation to a p-valent vertex of a graph n times, i.e. by replacing
each p-valent vertex of the graph by the complete graph Kp repeatedly, the corresponding
part of the obtained graph looks like Snp ; see Pisanski and Tucker [23] and Alspach and
Dobson [1]. The truncation operation on graphs has been generalized in several ways; see
Boben, Jajcay and Pisanski [2] and Exoo and Jajcay [6]. In [4], Eiben, Jajcay and Šparl
study automorphisms of generalized truncations. These constructions show significant sim-
ilarities to our construction, although they are distinct in general. A related construction,
called the clone cover, is considered by Malnič, Pisanski and Žitnik in [20].
In this paper we generalize the generalized Sierpiński graphs even further. Notice that
SnG can be viewed as an operation of S
n−1
G and G. This was a motivation for our introduc-
tion of the Sierpiński product of graphs. If we take any two graphs G and H , the resulting
product locally has the structure of H , but globally it is similar to G. The formal definition
of the Sierpiński product is given in Section 2.
The Sierpiński product shows some features of classical graph products, for instance
the vertex set of the Sierpiński product of two graphs G and H is V (G)×V (H). However,
to define the Sierpiński product of two graphs G and H , one needs some extra information
besides G and H . This information can be encoded as a function f : V (G) → V (H).
Furthermore, the product is defined so that we can extend it to multiple factors. We will
see that by definition the Sierpiński product of two graphs is always a subgraph of their
lexicographic product. Such layer-like structure also plays an important role in studying
symmetries of the Sierpiński product. For extensive information about graph products, see
the monograph by Hammack, Imrich and Klavžar [9].
The paper is organized as follows. In Section 2 we give a formal definition of the
Sierpiński product of two graphs G and H with respect to f : V (G) → V (H); this product
is denoted by G⊗fH . We explore some graph-theoretical properties such as connectedness
and planarity of a Sierpiński product. 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 and H must fulfill in order for G ⊗f H to be planar. In Section 3 we
study symmetries of the Sierpiński product of two graphs. We focus on the automorphisms
of G⊗f H that arise from the automorphisms of its factors and study the group generated
by these automorphisms. In several cases we can also describe the whole automorphism
group of G ⊗f H . Finally, in Section 4 we consider the Sierpiński product of more than
two graphs. A special case of n equal factors is considered.
2 Definition of the Sierpiński product and basic properties
Let us first review some necessary notions. All the graphs we consider are undirected,
simple and finite. Let G be a graph and x be a vertex of G. By N(x) we denote the set
of vertices of G that are adjacent to x, i.e. the neighbourhood of x. Vertices in this paper
will usually be tuples, but instead of writing them in vector form (xm, . . . , x1), we will
sometimes write them as words xm . . . x1 (especially in figures). More precisely, vertices
(0, 0, 0) or (0, (0, 0)) will simply be denoted by 000, except in the case when we will want
J. Kovič et al.: The Sierpiński product of graphs 5
to emphasize their origins. The number of vertices of a graph G, i.e. the order of G, will be
denoted by |G|, and the number of edges of G, i.e. the size of G, will be denoted by ||G||.
For other graph theory concepts not defined here we refer the reader to [21].
Definition 2.1. Let G,H be graphs and let f : V (G) → V (H) be a function. Then the
Sierpiński product of the 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) with two types of edges:
• {(g, h), (g, h′)} is an edge of G ⊗f H for every vertex g ∈ V (G) and every edge
{h, h′} ∈ E(H),
• {(g, f(g′), (g′, f(g))} is an edge of G⊗f H for every edge {g, g′} ∈ E(G).
If V (G) ⊆ V (H) and f is the identity function on its domain, we will skip the index
f and denote the corresponding Sierpiński product of G and H simply by G ⊗ H . Note
that there are no restrictions on the function f : V (G) → V (H). However, sometimes it
is convenient to assume that for every g, g1, g2 ∈ V (G), g1 ̸= g2, the following property
holds: if g1, g2 ∈ N(g), then f(g1) ̸= f(g2). In this case we say that f is locally injective.
a2 a3
a1
a4
b2 b3
b1
b4
c2 c3
c1
c4
1a 1b
1c
2a 2b
2c
3a 3b
3c
4a 4b
4c
Figure 3: The graph K3⊗f1 K4, where V (K3) = {a, b, c}, V (K4) = {1, 2, 3, 4}, f1(a) =
1, f1(b) = 2, f1(c) = 3, and the graph K4 ⊗f2 K3, where f2(1) = a, f2(2) = b, f2(3) =
c, f2(4) = c. The inner edges are solid while the connecting edges are dashed. The solid
subgraphs are aH, bH, cH for H = K4 and 1H, 2H, 3H, 4H for H = K3.
For any vertex g of G, the subgraph of G⊗f H induced by the set of vertices {(g, h) |
h ∈ V (H)} is called the subgraph associated with g and is denoted by gH . We may view
the graph G⊗fH as partitioned into graphs gH , one for every vertex g of G, and connecting
for every edge {g, g′} ∈ E(G) the corresponding vertex f(g) in g′H to the vertex f(g′) in
gH . The edges of G ⊗f H naturally fall into two classes. The edges connecting different
subgraphs gH are called connecting edges, while the edges inside some subgraph gH are
called inner edges. Given gH , we may add its neighbourhood, i.e. all connecting edges
and their endvertices, to obtain a graph denoted by gHN . If we identify all newly added
vertices to a single vertex, denoted by gH , we obtain a graph, denoted by H + g.
Example 2.2. Figure 3 (left) shows the Sierpiński product of K3 and K4 with respect
to the following function f1. The vertices of K3 are labelled with letters a, b, c, the ver-
tices of K4 are labelled with numbers 1, 2, 3, 4 and f1 : V (K3) → V (K4) is given by
6 Ars Math. Contemp. 23 (2023) #P1.01
f1(a) = 1, f1(b) = 2, f1(c) = 3. Figure 3, right, shows the Sierpiński product of K4
and K3 with respect to f2 : V (K4) → V (K3) defined by f2(1) = a, f2(2) = b, f2(3) =
c, f2(4) = c. This shows that the Sierpiński product is not commutative. Figure 4 depicts
examples of the graphs gHN and H + g in K3 ⊗f1 K4 and K4 ⊗f2 K3.
a2
b2 b3
b1
b4
c2 1a 1b
1c
2a
3a
4a
b2 b3
b1
b4
bK4 1a 1b
1c
1K3
Figure 4: Top: the graphs bHN for H = K4 and 1HN for H = K3. Bottom: the graphs
H + b for H = K4 and H + 1 for H = K3.
2.1 Basic properties of the Sierpiński product of graphs
We now state some observations regarding the structure of the Sierpiński product of two
graphs. We omit most of the proofs, since they follow straight from the definition.
Proposition 2.3. Let G,H be graphs and let f : V (G) → V (H) be a function. Then the
following statements hold.
(i) If |G| = 1, then G⊗f H is isomorphic to H .
(ii) If |H| = 1, then G⊗f H is isomorphic to G.
Lemma 2.4. Let G,H be graphs and let f : V (G) → V (H) be a function. Let G′, H ′
be subgraphs of G,H , respectively, and let f ′ be the restriction of f to V (G′) such that
Im(f ′) ⊆ V (H ′). Then the graph G′ ⊗f ′ H ′ is a subgraph of the graph G⊗f H .
The following result explains the role of the graphs G and gH in G⊗f H .
Lemma 2.5. Let G,H be graphs, and let f : V (G) → V (H) be a function. Then the
following statements hold.
J. Kovič et al.: The Sierpiński product of graphs 7
(i) For every vertex g of G, the subgraph gH of G⊗f H is isomorphic to H .
(ii) If, in addition, the graph H is connected, then the graph G is a minor of G⊗f H .
(iii) In particular, if the graph H is connected and the graph G⊗f H is planar, then the
graphs G and H are planar.
Notice that planarity of both factors G and H in (iii) easily follows from the fact that
H is a connected subgraph, and G is a minor of G⊗f H . However, if H is not connected,
the conclusion in (ii) that G is a minor of G ⊗f H does not necessarily follow, since we
cannot simply contract every subgraph gH of G⊗f H to a single vertex. This is shown by
the following example.
Example 2.6. Take G to be K5 with vertices from 1 to 5 and H to be two isolated vertices,
denoted by a and b, and then let f map 1 and 2 from K5 to a of H and the remaining three
vertices of K5 to b of H . The resulting graph G ⊗f H is isomorphic to the disjoint union
of K2,K3 and K2,3 and is therefore planar. Hence, it cannot have K5 as a minor.
Proposition 2.7. Let G,H be graphs and let f : V (G) → V (H) be a function. Then the
graph G⊗f H has |G| · |H| vertices and ||H|| · |G|+ ||G|| edges. In particular, G⊗f H
has ||H|| · |G| inner edges and ||G|| connecting edges.
Lemma 2.8. Let G and H be graphs and let f : V (G) → V (H) be a function. Then the
following holds.
(i) For every g, g′ ∈ V (G) there exists at most one edge connecting graphs gH and
g′H . In addition, graphs gH and g′H are joined by an edge if and only if vertices g
and g′ are adjacent in graph G.
(ii) If a vertex g ∈ V (G) has d neighbours in G, then there are d vertices and d edges
belonging to gHN that are not a part of gH . These d edges are connecting edges.
(iii) The function f is locally injective if and only if the connecting edges form a matching
in G⊗f H or, equivalently, if and only if every vertex of G⊗f H is an endvertex of
at most one connecting edge.
Proof. (i) Only an edge of form {(g, f(g′)), (g′, f(g))} can connect graphs gH and g′H
and this happens if and only if there exists an edge between g and g′. Hence, there exists a
bijective correspondence between the connecting edges of G⊗f H and the edges of G.
(ii) This follows from (i) and the fact that the connecting edges with an endvertex in gH
are in bijective correspondence with the edges connecting g to its neighbours in G.
(iii) For every g ∈ V (G), the connecting edges leading from gH to the rest of the graph
G ⊗f H have distinct endvertices outside gH . If f is locally injective, they have distinct
endvertices within gH . It follows that no two connecting edges share a common endvertex,
so the connecting edges form a matching in G ⊗f H . Conversely, if f fails to be locally
injective, then at least two connecting edges share a common endvertex.
The lexicographic product of two graphs G and H is the graph G ◦H with vertex set
V (G) × V (H) and two vertices (g, h) and (g′, h′) are adjacent in G ◦ H if and only if
either g is adjacent with g′ in G or g = g′ and h is adjacent with h′ in H . For g ∈ V (G),
we denote by gH the subgraph of G ◦H induced by the set {(g, h)|h ∈ V (H)}. Then the
8 Ars Math. Contemp. 23 (2023) #P1.01
graph G ◦H consists of |G| copies of H , and for every edge {g, g′} in G, every vertex of
gH is connected to every vertex in g′H . Therefore, the next result follows straight from
Definition 2.1.
Proposition 2.9. Let G and H be graphs and let f : V (G) → V (H) be a function. Then
the graph G⊗f H is a spanning subgraph of the lexicographic product G ◦H .
Note that for different functions f, f ′, the graphs G ⊗f H and G ⊗f ′ H may be iso-
morphic or nonisomorphic.
Proposition 2.10. Let G,H be graphs and let f : V (G) → V (H) be a function. Let
α ∈ Aut(G), β ∈ Aut(H) and f ′ = β ◦ f ◦ α. Then G⊗f H is isomorphic to G⊗f ′ H .
Proof. Define the function γ : V (G⊗f H) → V (G⊗f ′ H) by γ(g, h) = (α−1(g), β(h))
for g ∈ V (G) and h ∈ V (H). Since α, β are bijections, γ is also a bijection. Since β is an
automorphism, γ maps inner edges to inner edges.
Take a connecting edge in G ⊗f H , say {(g, f(g′)), (g′, f(g))}, where {g, g′} ∈
E(G). Then γ(g, f(g′)) = (α−1(g), β(f(g′)) and γ(g′, f(g)) = (α−1(g′), β(f(g)).
Since f ′(α−1(g)) = β(f(α(α−1(g)))) = β(f(g)) and f ′(α−1(g′)) = β(f(α(α−1(g′)))) =
β(f(g′)), we see that γ also maps a connecting edge to a connecting edge. Therefore γ is
an isomorphism.
Corollary 2.11. Let G be a graph and let f ∈ Aut(G). Then G ⊗ G is isomorphic to
G⊗f G.
In the remainder of this section we consider when the Sierpiński product of two graphs
is connected.
Proposition 2.12. Let G and H be graphs and let f : V (G) → V (H) be a function. Then
G⊗f H is connected if and only if G and H are connected.
Proof. Suppose G and H are connected. Then G⊗f H is connected by Definition 2.1 and
Lemma 2.5.
Conversely, suppose G ⊗f H is connected. Pick two vertices g and g′ from G. Then
a path from gH to g′H in G ⊗f H corresponds to a path in G from g to g′. Therefore,
G is also connected. Suppose now that H is not connected. Denote by H1 a connected
component of H such that V1 = {g ∈ G| f(g) ∈ V (H1)} is nonempty. Take any vertices
g ∈ V1 and h ∈ V (H1). If there exists an edge of form {(g, h), (g′, f(g))}, then h = f(g′),
so g′ ∈ V1. Note that f(g) ∈ V (H1). Therefore, all the neighbours of (g, h) belong either
to gH1 or to g′H1 for some g′ ∈ V1. It follows that there are no edges between the set of
vertices {(g, h) ∈ V (G ⊗f H)| g ∈ V1 and h ∈ V (H1)} and the rest of the vertices of
G⊗fH . So G⊗fH is not connected. This is a contradiction, so H must be connected.
In [19], Klavžar and Zemljič have characterized which generalized Sierpiński graphs
are k-connected and k-edge connected. Unfortunately, their results do not carry over di-
rectly to the Sierpiński product of distinct graphs since the factors may have different con-
nectivity properties. Moreover, the result does not depend only on the connectivity of its
factors, but also on the choice of the function f . For instance, C5 ⊗ C5 is 2-connected.
However, for a constant function f , the product C5 ⊗f C5 is only 1-connected.
J. Kovič et al.: The Sierpiński product of graphs 9
2.2 Planarity
In this section we study planarity of the Sierpiński product G ⊗f H of graphs G and H
with respect to a function f : V (G) → V (H). We have already mentioned in Lemma 2.5
that for a connected graph H , planarity of the graph V (G⊗f H) implies planarity of both
factors. The next theorem characterizes when a Sierpiński product G⊗fH is planar when f
is a locally injective function. Recall that the construction of a graph H+g was introduced
in the beginning of Section 2.
Theorem 2.13. Let G be a 2-connected graph or G = K2, let H be a connected graph and
let f : V (G) → V (H) be a locally injective function. Then the graph G⊗f H is planar if
and only if the following three conditions are fulfilled:
(i) the graphs G and H are planar,
(ii) for every g ∈ V (G) the graph H + g is planar,
(iii) there exists an embedding of the graph G in the plane with a chosen orientation
which has the following property: for every g ∈ V (G), with g1, g2, . . . , gk being the
cyclic order of vertices around the vertex g, there exists an embedding of the graph
H + g in the plane such that the cyclic order of vertices around the vertex gH in
graph H + g is f(gk), f(gk−1), . . . , f(g1).
Proof. The fact that f is a locally injective function simplifies the arguments. Namely, all
the vertices in N(g) are distinct for every g ∈ V (G).
(⇒) First, assume that the graph G ⊗f H is planar. Then, the graphs G,H are planar
by Lemma 2.5 and (i) is established.
Suppose G ⊗f H is embedded in the plane. Note that for every g ∈ V (G), the
embedding of G ⊗f H induces a planar embedding of gH . For every g ∈ V (G), let
N(gH) = {g′H|g′ ∈ N(g)} denote the collection of graphs g′H that are adjacent to gH .
Since the graph G is 2-connected, or G = K2, and the graph H is connected, all the graphs
from N(gH) are inside the same face Fg of the graph gH (otherwise the vertex g would be
a cut vertex in G). For a fixed g0 we may assume that Fg0 is the outer face of g0H . If not,
we take a different stereographic projection of G⊗f H . But then, for every g ∈ V (G), the
corresponding face Fg is the outer face of gH . Hence, we may contract every graph gH to
a single vertex. From now on we assume that the graph G⊗f H is embedded in the plane
as we just explained and choose an orientation of the plane. If we contract every subgraph
gH of G ⊗f H to a single vertex, we obtain a minor of G ⊗f H which is isomorphic to
G. Its planar embedding is determined from the planar embedding of G⊗f H . Hence, for
every vertex of G the cyclic order of its neighbours is defined.
Now again take the embedding of G ⊗f H as described above. Take an arbitrary
g ∈ V (G) and consider the subgraph gHN that inherits the planar embedding and has
all of its pending edges attached to the vertices in the outer face of gH . This establishes
a planar embedding of H + g, which, in turn, is obtained from gHN by a suitable vertex
identification. This proves (ii).
Now it is easy to see that the embedding of G, obtained from G ⊗f H by contracting
every copy of H to a single vertex, fulfills (iii). Namely, the cyclic order g1, g2, . . . , gk of
vertices around a vertex g of G in this embedding corresponds to the ordering of the vertices
(g, f(g1)), (g, f(g2)), . . . , (g, f(gk)) around the outer face of gH in the planar embedding
of G ⊗f H . The cyclic order of vertices around gH in the planar embedding of gH + g
10 Ars Math. Contemp. 23 (2023) #P1.01
described above is then (g, f(gk)), (g, f(gk−1)), . . . , (g, f(g1)). Therefore, an appropriate
embedding of H + g exists for every g ∈ V (g).
(⇐) The converse is proved by construction. By (i), the graphs G and H are planar.
Moreover, by (ii), for every g ∈ V (G), the graph H + g is planar. Using (iii), we embed
the graph G in the plane. Then for each vertex g of G, we replace the vertex g by the planar
embedding of the graph gH , induced by the embedding of H + g from (iii). Again by
(iii), it is possible to connect the copies of H among themselves in such a way that a planar
embedding of the resulting graph, isomorphic to G⊗f H , is obtained.
We believe that Theorem 2.13 holds also if the function f is not locally injective. How-
ever, the arguments in the proof become much more involved in this case.
Remark 2.14. Note that the condition in Theorem 2.13 that the graph G is 2-connected
is essential. For example, take G to be the graph obtained from K4 (whose vertices are
denoted by 1, 2, 3, 4) by adding a new vertex (named 5) to it and joining it to the vertex 4
only. The graph G⊗G is then planar, but G+4 is not and the condition (ii) in Theorem 2.13
does not hold. See Figure 5.
2 3
4
1
5
2 3
4
1
5 4G
Figure 5: The graph G is planar but not 2-connected. The graph G+ 4 contains a subdivi-
sion of K5 and is not planar.
The next result is evident from the proof of Theorem 2.13.
Corollary 2.15. Let G be a 2-connected graph or G = K2, let H be a connected graph
and let f : V (G) → V (H) be a locally injective function. If the graph G ⊗f H is planar,
then for every g ∈ V (G) there exists an embedding of the graph H in the plane such that
the vertices {f(g′); g′ ∈ N(g)} lie on the boundary of the same face.
Using Theorem 2.13 we can now determine when the graph G ⊗ G is planar for a
connected graph G. We also give a sufficient condition for the graph G⊗f H to be planar
when G ̸= H . By a block we mean a maximal connected subgraph of a given graph that
has no cut-vertices. Note that a block with more than two vertices is 2-connected.
Theorem 2.16. Let G be a connected graph. Then the graph G⊗G is planar if and only
if every block of G is outerplanar or equal to K4.
Proof. Note that for every block B of G, the identity function V (B) → V (B) is locally
injective. So we may use Theorem 2.13 and Corollary 2.15 for every block of G.
J. Kovič et al.: The Sierpiński product of graphs 11
First assume that the graph G ⊗ G is planar. Let B be a block of G. Suppose that B
is planar but it is not outerplanar or equal to K4. Then it contains a subdivision of K2,3
or a subdivision of K4 (with at least one additional vertex) as a subgraph, see [3]. Such a
graph B always contains a vertex such that in every planar embedding of B, not all of its
neighbours will be on the boundary of the same face. Therefore B ⊗ B is not planar by
Corollary 2.15. On the other hand, B ⊗ B is a subgraph of G ⊗G by Lemma 2.4, so it is
planar. A contradiction. Therefore, the graph B must be outerplanar or equal to K4.
We prove the converse by induction on the number of blocks of the graph G. If G has
just one block that is outerplanar or equal to K4, then the conditions (i), (ii), (iii) from
Theorem 2.13 are fulfilled, so G⊗G is planar.
Suppose now that G has more than one block and that every block of G is outerplanar
or equal to K4. Let B be a block that corresponds to a leaf in the block-cut tree of G and
let v be the only cut vertex of G contained in B. Let G′ be the graph obtained from G by
deleting all the vertices of B with the exception of v. Then the graph G′ has one block
less than G and, by the induction hypothesis, the graph G′ ⊗ G′ is planar. Take a planar
embedding of G′ ⊗ G′. We obtain a planar embedding of G ⊗ G in the following way.
We take a planar embedding of B in which v appears on the boundary of the outer face;
moreover if B is outerplanar, we take an embedding of B such that every vertex of B lies
on the boundary of the outer face. For every g ∈ V (G′), we insert a copy of B in a face of
gG′ that contains the vertex (g, v) and then identify the vertex (g, v) with the vertex v of
B. We denote the graph obtained so far by K. Observe that K is embedded in the plane.
To the graph K we still need to add a copy of G for every vertex of B except v. These
copies of G are connected only to the copies of G in G ⊗ G corresponding to the vertices
of B. Choose an orientation of the plane. Now we consider two cases.
First, let B = K4, with vertices v, v1, v2, v3. Any three vertices of B are on the bound-
ary of a same face in every embedding of B in the plane. Therefore, in the subgraph vG of
K there exists a face such that the vertices (v, v1), (v, v2), (v, v3) all lie on its boundary;
without loss of generality we may assume that they are arranged in this order (with respect
to the chosen orientation of the plane). We may embed the graph v1G in the plane such that
the vertices (v1, v), (v1, v3), (v1, v2) lie on the outer face in this order, likewise, we may
embed the graph v2G in the plane such that the vertices (v2, v), (v2, v1), (v2, v3) lie on the
outer face in this order, and we may embed the graph v3G in the plane such that the vertices
(v3, v), (v3, v2), (v3, v1) lie on the outer face in this order. Now place viG in the face of the
subgraph vG of K that contains the vertices (v, v1), (v, v2), (v, v3) close to vertex (v, vi)
and connect vertices (v, vi) and (vi, v), for i = 1, 2, 3. The graphs viG are embedded
in the plane such that it is possible to also connect the pairs of vertices (v1, v2), (v2, v1),
(v1, v3), (v3, v1) and (v2, v3), (v3, v2) without crossings. This gives us a planar embedding
of the graph G⊗G.
Next, let B be outerplanar. The subgraph vG of K is embedded in the plane and it
contains a copy of B such that all the vertices of B are on the boundary of the same face of
K, say F . We consider a planar embedding of the graph G in which all the vertices of the
block B are on the boundary of the outer face and in the reverse order as the corresponding
vertices in vG. For every vertex u of B except v, we place such a copy of G with vertex
set {u} × V (G) into face F close to the vertex (v, u). Then we connect vertices (v, u)
and (u, v) with an edge if u is a neighbour of v in G. The graphs uG, u ∈ V (B)\{v}
are now all in the same face of K. Moreover, the subgraphs uB, u ∈ V (B)\{v}, are
all in the same face of K with all their vertices on the boundary of the outer face (of the
12 Ars Math. Contemp. 23 (2023) #P1.01
embedding of uG in the plane) and the order of these vertices is reversed compared to the
order of the corresponding vertices in vB. Note that the cyclic order of the graphs uB,
u ∈ V (B)\{v} is the same as the order of the corresponding vertices in vB. Therefore, it
is possible to connect the vertices (u, u′) and (u′, u) for every edge {u, u′} of B without
crossings. Again we obtain a planar embedding of the graph G ⊗ G. This completes the
proof.
Theorem 2.17. Let G,H be connected graphs and let f : V (G) → V (H) be a function.
Assume that G is planar, ∆(G) ≤ 3 and H is outerplanar. Then G⊗f H is planar.
Proof. Denote K = G ⊗f H for convenience. Suppose K is not planar. Then it contains
a subdivision of K3,3 or K5 as a subgraph. First assume that K contains a subdivision of
K3,3. Denote the set vertices of degree 3 of the subdivision of K3,3 in K by X . There are
four cases to consider, depending on how many vertices from X are in the same copy of H
in K.
1. Every vertex from X is in a separate copy of H . If no path connecting two vertices
from X passes through any other copies of H containing vertices from X , and at
most one such path passes through every copy of H not containing vertices from X ,
then by contracting gH to a single vertex, for every g ∈ V (G), we see that K3,3 is
a minor in G, so G is not planar. Otherwise we need at least four edges connecting
some copy of H to the other copies of H in K. This is not possible, since the
maximal degree in G is at most three.
2. There are between two and four vertices from X in some gH . Then we need at least
four edges connecting gH to the other copies of H in K. This is again not possible,
since the maximal degree of G is at most 3.
3. There are five vertices from X in some gH and one vertex from X in some g′H for
g ̸= g′. Since H is outerplanar, gH cannot contain a subdivision of K2,3. Therefore,
we need at least two edges going out of gH to obtain a subdivision of K2,3 from the
five vertices in gH . We also need three edges going out of gH to connect gH to the
vertex of K3,3 in g′H . This is again not possible, since the maximal degree of G is
at most 3.
4. The only remaining possibility is that all six vertices from X are in the same copy gH
of H . Since H is outerplanar, there can be at most seven edges (or paths) between
pairs of vertices of K3,3 in gH . The remaining two paths must go through the other
copies of H , which means that we again need at least four edges connecting gH to
the other copies of H in K. A contradiction.
Therefore, K does not contain a subdivision of K3,3. Next assume that K contains a
subdivision of K5. Denote the set vertices of degree 4 of the subdivision of K5 in K by Y .
There are two cases to consider, depending on how many vertices from Y are in the same
copy of H .
1. There are between one and four vertices from Y in some gH . Then we need at least
four edges connecting gH to the other copies of H in K. This is not possible, since
the maximal degree in G is at most three.
J. Kovič et al.: The Sierpiński product of graphs 13
2. All five vertices from Y are in the same copy of H . Since H is outerplanar, it does
not contain a subdivision of K4 or K2,3. Therefore, there can be at most eight edges
(or paths) between pairs of these vertices in gH (in fact, there can be at most six
such paths). The remaining two paths must go through other copies of H , which
means that we need at least four edges connecting gH to other copies of H in K. A
contradiction.
It follows that K does not contain a subdivision of K3,3 or K5, so it is planar.
If a connected graph is not planar, it is natural to consider its genus. The genus of a
graph G is denoted by γ(G). Recall that by Lemma 2.5, if the graph H is connected, the
graph G is a minor of G⊗f H for any function f : V (G) → V (H), and the graph G⊗f H
contains |G| copies of the graph H as induced subgraphs. Suppose G,H are connected
and f is arbitrary. Then it is easy to see, cf. [21, Theorem 4.4.2], that
γ(G⊗f H) ≥ γ(G) + |G| · γ(H). (2.1)
Note that the bound is not sharp even if the factors are planar. In the case of a planar
Sierpiński product, we were able to settle the case in Theorem 2.13. It would be interest-
ing to find some sufficient condition for the equality in (2.1) to hold also for non-planar
Sierpiński products.
3 Symmetries of the Sierpiński product of graphs
Throughout this section let G,H be connected graphs and let f : V (G) → V (H) be a
function. Recall that the edge set of G⊗f H can be naturally partitioned into two subsets:
• inner edges {(g, h), (g, h′)} for every vertex g ∈ V (G) and every edge {h, h′} ∈
E(H), and
• connecting edges {(g, f(g′), (g′, f(g))} for every edge {g, g′} ∈ E(G).
We call this partition of the edge set the fundamental edge partition. We will say that an
automorphism of G⊗f H respects the fundamental edge partition if it takes inner edges to
inner edges and connecting edges to connecting edges. We denote the set of all automor-
phisms of G ⊗f H that respect the fundamental edge partition by Ã(G,H, f). This set is
a subgroup of the whole automorphism group of G⊗f H . For connected graphs G and H ,
the automorphisms that respect the fundamental edge partition have the following useful
property.
Proposition 3.1. Let G and H be connected graphs. Then every automorphism γ̃ ∈
Ã(G,H, f) permutes the subgraphs gH , g ∈ G. Moreover, the restriction γ̃|V (gH) :
V (gH) → V (g′H), where g′ ∈ V (G), is a graph isomorphism.
In this section we first show that every automorphism of G ⊗f H that respects the
fundamental edge partition induces automorphisms of G and H . And conversely, we define
two families of automorphisms of G ⊗f H that respect the fundamental edge partition
using automorphisms of G and H . As it turns out, one of them is a subfamily of the
other one. Then we show that in several cases all the automorphisms of G ⊗f H respect
the fundamental edge partition. Finally, we focus on the case when G = H and f is an
automorphism. In this case we can completely describe the group of automorphisms that
respect the fundamental edge partition.
14 Ars Math. Contemp. 23 (2023) #P1.01
3.1 Automorphisms that respect the fundamental edge partition
Let γ̃ be an automorphism of G⊗f H that respects the fundamental edge partition. Then,
it permutes the subgraphs gH , g ∈ G. Define the function γ : V (G) → V (G) such
that γ(g) = g′ if γ̃ maps gH to g′H . Obviously, γ is a bijection. Let {g, g1} be an
edge of G. Then {(g, f(g1)), (g1, f(g))} is a connecting edge of G ⊗f H . Since γ̃ re-
spects the fundamental edge partition, it maps this edge to another connecting edge, say
{(g′, f(g′1)), (g′1, f(g′))}, where g′ and g′1 are adjacent in G. But then γ maps the edge
{g, g1} to an edge (i.e. to {g′, g′1}) and γ is an automorphism. We will say that γ is the pro-
jection of γ̃ on G. Conversely, γ̃ is a lift of γ. Note that the projection of γ̃ ∈ Aut(G⊗f H)
on G is uniquely defined. However, given an automorphism of G, it can have a unique lift,
more than one lift or none at all.
On the other hand, the application of γ̃ on every copy of gH in G ⊗f H induces an
automorphism γg of H , defined by γg(h) = h′ if γ̃ sends (g, h) to (g1, h′) for some
g1 ∈ V (G) and h′ ∈ V (H).
We will now introduce the first family of automorphisms of G⊗fH that can be obtained
from automorphisms of G and H . All such automorphisms respect the fundamental edge
partition.
Definition 3.2. Let G,H be connected graphs and let f : V (G) → V (H) be a function.
Let α ∈ Aut(G) and let B : V (G) → Aut(H) be a function. For simplicity we will write
βg instead of B(g) for g ∈ V (G). Define the function Ψ(α,B) : V (G⊗fH) → V (G⊗fH)
by
Ψ(α,B) : (g, h) 7→ (α(g), βg(h)).
If B is a constant function, say βg = β for all g ∈ V (G), we denote Ψ(α,B) by Ψ(α, β).
By the discussion at the beginning of this section, we may conclude that the following
holds.
Theorem 3.3. Let G,H be connected graphs and let f : V (G) → V (H) be a function.
Then, every automorphism of G ⊗f H that respects the fundamental edge partition is of
form Ψ(α,B) for some α ∈ Aut(G) and some function B : V (G) → Aut(H).
We now determine when the function Ψ(α,B) from Definition 3.2 is an automorphism.
In Propositions 3.4, 3.5, 3.6 and Corollaries 3.7, 3.8, and 3.9, the assumptions from Defi-
nition 3.2 hold.
Proposition 3.4. The function Ψ(α,B) is a bijection.
Proof. It is enough to prove that Ψ(α,B) is injective. This is straightforward since α and
βg , g ∈ V (G), are all injective.
Proposition 3.5. The function Ψ(α,B) is an automorphism if and only if for every g ∈
V (G) we have f ◦ α = βg ◦ f on N(g). Moreover, in this case Ψ(α,B) respects the
fundamental edge partition.
Proof. We first show that Ψ(α,B) always maps an inner edge to an inner edge. To see
this, let e = {(g, h1), (g, h2)} be an inner edge. Then Ψ(α,B) maps the edge e to
{(α(g), βg(h1)),(α(g), βg(h2))}, which is an inner edge since βg is an automorphism of
H .
J. Kovič et al.: The Sierpiński product of graphs 15
Suppose now that Ψ(α,B) is an automorphism. Since Ψ(α,B) maps inner edges to
inner edges, it must map connecting edges to connecting edges. Let e = {(g, f(g1)),
(g1, f(g))} be a connecting edge. Then Ψ(α,B)(e) = {(α(g), βg(f(g1))), (α(g1),
βg1(f(g)))} is also a connecting edge. Therefore f(α(g1)) = βg(f(g1)). Since g1 can
be any neighbour of g in G, we have f ◦ α = βg ◦ f on N(g).
Conversely, let f ◦ α = βg ◦ f on N(g) for every g ∈ V (G). Let e = {(g, f(g1)),
(g1, f(g))} be a connecting edge in G ⊗f H . Then Ψ(α,B)(e) = {(α(g), βg(f(g1))),
(α(g1), βg1(f(g)))}. Since f(α(g)) = βg1(f(g)) and f(α(g1)) = βg(f(g1)), Ψ(α,B)(e)
is a connecting edge. Therefore, Ψ(α,B) is an automorphism.
Proposition 3.6. The function Ψ(α, β) is an automorphism if and only if f ◦ α = β ◦ f .
Proof. Let f ◦ α = β ◦ f on N(G) for every g ∈ V (G). Since G is connected, it has no
isolated vertices, and so f ◦ α = β ◦ f on V (G). The claim then follows from Proposi-
tion 3.5.
A few special cases now follow as simple corollaries. Recall that α, β,Ψ(α, β) are
defined in Definition 3.2.
Corollary 3.7. Suppose G = H and f is a bijective function. Then the function Ψ(α, β)
is an automorphism if and only if β = f ◦ α ◦ f−1.
Corollary 3.8. Suppose G = H and f is the identity function. Then the function Ψ(α, β)
is an automorphism if and only if α = β.
Corollary 3.9. Suppose V (G) ⊆ V (H), f is the identity function on its domain and
β|V (G) = α. Then the function Ψ(α, β) is an automorphism.
Remark 3.10. If f is injective and G ̸= H , we can always relabel the vertices of G,H
such that f is the identity on its domain.
We now give some examples showing that f need not be injective or surjective and we
can still have automorphisms of type Ψ(α,B).
Example 3.11. Let G = K3 and H = K3,3 with V (G) = {1, 2, 3} and V (H) =
{1, 2, . . . , 6}, with adjacencies as in Figure 6. Let f : V (G) → V (H) map 1 7→ 1, 2 7→ 3,
3 7→ 5. Let α = (1 2 3), β1 = (1 3 5)(2 4 6), β2 = (1 3 5)(2 6 4), β3 = (1 3 5) and let
B : V (G) → Aut(G) be defined by B(g) = βg . Then f ◦ α = β1 ◦ f = β2 ◦ f = β3 ◦ f
and
Ψ(α,B) = (11 23 35)(12 24 32)(13 25 31)(14 26 34)(15 21 33)(16 22 36)
is an automorphism of G⊗f H that cyclically permutes the subgraphs gH , see Figure 6.
Example 3.12. Let G = H = K1,3 with the edge set {{1, 2}, {2, 3}, {2, 4}}, and let
f : V (G) → V (G) be defined as f = (1 2 3 4). Note that f is a bijection that is not an
automorphism of G. If α = (3 4) and β = f ◦ α ◦ f−1 = (1 4), then f ◦ α = β ◦ f and
Ψ(α, β) = (11 14)(21 24)(31 44)(32 42)(33 43)(34 41)
is an automorphism of G⊗f G, that swaps the copies 3G and 4G, see Figure 7.
16 Ars Math. Contemp. 23 (2023) #P1.01
1
2 3 3 4
5
61
2
13 14
15
1611
12
23 24
25
2621
22 32
33 34
35
36
31
Figure 6: The graphs K3, K3,3 and their Sierpiński product with respect to f : V (K3) →
V (K3,3), f : 1 7→ 1, 2 7→ 3, 3 7→ 5.
1
2
3 4
22
13
12
24 21
23
3332 43
42
31
34 44
41
1411
Figure 7: The graph G = K1,3 and the Sierpiński product G ⊗f G with respect to f =
(1 2 3 4).
Example 3.13. Let G = C4 with V (G) = {1, 2, 3, 4} and adjacencies as in Figure 8, and
let H be a star K1,3, with the edge set {{1, 2}, {2, 3}, {2, 4}}. Let f : V (G) → V (H)
map 1 7→ 2, 2 7→ 2, 3 7→ 4 and 4 7→ 3. Note that the function f is neither injective nor
surjective. If α = (1 2)(3 4) and β = (3 4), then f ◦ α = β ◦ f and
Ψ(α, β) = (11 21)(12 22)(13 24)(14 23)(31 41)(32 42)(33 44)(34 43)
is a reflection automorphism of G ⊗f H , swapping the copies 1H, 2H and 3H, 4H , see
Figure 8.
Now let us introduce the second family of automorphisms of G ⊗f H . Let g ∈ V (G)
and β ∈ Aut(H). Define the function Φ(g, β) : V (G⊗f H) → V (G⊗f H) by
Φ(g, β) : (g1, h1) 7→
{
(g1, h1) if g1 ̸= g,
(g1, β(h1)) if g1 = g.
J. Kovič et al.: The Sierpiński product of graphs 17
1
2
3 4
4
1 2
3
32
3344
42
13
12 22
24
11
14
21
23
31
34
41
43
Figure 8: The graphs C4, K1,3 and their Sierpiński product with respect to f : V (C4) →
V (K1,3), f : 1 7→ 2, 2 7→ 2, 3 7→ 4, 4 7→ 3.
Proposition 3.14. Let g ∈ V (G) and let β ∈ Aut(H). The function Φ(g, β) is an auto-
morphism of G ⊗f H if and only if β is in the pointwise stabilizer of f(N(g)). Moreover,
in this case Φ(g, β) respects the fundamental edge partition.
Proof. The function Φ(g, β) is obviously a bijection since it fixes all the vertices of G⊗fH
not in gH and it permutes the vertices in gH . It also fixes the inner edges and connecting
edges that do not have any endvertices in gH and it permutes the inner edges in gH .
Take a vertex g′ ∈ N(g). Then {(g, f(g′)), (g′, f(g))} is a connecting edge. The
function Φ(g, β) maps {(g, f(g′)), (g′, f(g))} to the set {(g, β(f(g′)), (g′, f(g))}, which
is an edge if and only if β(f(g′)) = f(g′). So Φ(g, β) is an automorphism if and only if β
is in the stabilizer of f(g′) for every g′ ∈ N(G).
Remark 3.15. Note that by Theorem 3.3, the function Φ(g, β) is the same as Ψ(α,B)
for some α ∈ Aut(G) and B : V (G) → Aut(H). Indeed, it is easy to verify that for
α = id and B defined by the rules B : g1 → id if g1 ̸= g and B : g → β, we have
Φ(g, β) = Ψ(α,B).
Given a group X acting on a set Y , we denote by X(Y ) the pointwise stabilizer of Y ,
i.e. the subgroup of X that fixes every element of Y . For g ∈ G denote by B̂g(G,H, f) the
group generated by {Φ(g, βg)|βg ∈ Aut(H)(f(N(g)))}. Denote by B̂(G,H, f) the group
generated by {B̂g(G,H, f)| g ∈ V (G)}. We will now study the structure of the group
B̂(G,H, f).
Proposition 3.16. Let g, g′ be distinct vertices of G and let βg ∈ Aut(H)(f(N(g))),
βg′ ∈ Aut(H)(f(N(g′))). Then Φ(g, βg) and Φ(g′, βg′) commute.
18 Ars Math. Contemp. 23 (2023) #P1.01
14
15
16
12
11
13
21
26
25
23
24
22
32
36
35
34
33
31
43
45
46
41
42
44
1
2 3
4
6 5
4
3
1
2
Figure 9: The graphs C4, 2K3 + e and their Sierpiński product with respect to f = id.
Proof. The functions Φ(g, βg) and Φ(g′, βg′) commute since as permutations they have
disjoint supports.
Theorem 3.17. The group B̂(G,H, f) is a subgroup of the group Ã(G,H, f) and is a
direct product
B̂(G,H, f) =
∏
g∈V (G)
B̂g(G,H, f). (3.1)
Moreover, the group B̂(G,H, f) is isomorphic to the group
∏
g∈V (G) Aut(H)(f(N(g))).
Proof. The group B̂(G,H, f) is a subgroup of the group Ã(G,H, f) by definition and
Propositon 3.14. The groups B̂g(G,H, f), g ∈ V (G), have pairwise only the identity
in common, they generate the group B̂(G,H, f), and the elements of two distinct groups
B̂g(G,H, f) commute, therefore equation (3.1) holds. The last claim is true since for
every g ∈ G, the groups B̂g(G,H, f) and Aut(H)(f(N(g))) are isomorphic in the obvious
way.
3.2 When do all the automorphisms respect the fundamental edge partition
Given connected graphs G,H and a function f : V (G) → V (H), in general there can exist
automorphisms of G ⊗f H that do not respect the fundamental edge partition. Figure 9
shows such an example. There, G = C4, H = 2K3 + e and f : V (G) → V (H) is the
identity function on its domain. One can easily observe that by rotating the graph G⊗f H ,
the inner edge {16, 15} can be mapped to the connecting edge {14, 41}.
Note that in the example above, the graph H is not 2-connected. When two graphs
G and H are both 2-connected, we have so far not been able to find an automorphism of
J. Kovič et al.: The Sierpiński product of graphs 19
G ⊗f H that does not respect the fundamental edge partition. Therefore, we propose the
following conjecture.
Conjecture 3.18. Let G,H be 2-connected graphs and let f : V (G) → V (H) be a func-
tion. Then
Ã(G,H, f) = Aut(G⊗f H).
In this section we prove this conjecture for two special cases. In the first case G =
H, f ∈ Aut(G) and G is a regular triangle-free graph. In the second case every edge of
H is contained in a short cycle. Note that in these two cases the assumption that G,H are
2-connected is not needed.
Theorem 3.19. Let G be a connected regular triangle-free graph and let f : V (G) →
V (G) be an automorphism of G. Then every automorphism of G⊗f G respects the funda-
mental edge partition. In other words,
Ã(G,G, f) = Aut(G⊗f G).
Proof. Let k denote the valency of G. Then the endvertices of every connecting edge in
G ⊗f G have valency k + 1 by Lemma 2.8. An endvertex of an inner edge may have
valency k or k + 1. Clearly, if at least one endvertex of an inner edge has valency k, this
edge cannot be mapped to a connecting edge by any automorphism.
Suppose now that both endvertices of an inner edge {(g, g1), (g, g2)} have degree k+1.
This is only possible if (g, g1) and (g, g2) are the endvertices of some connecting edges,
say {(g, g1), (g′1, f(g))} and {(g, g2), (g′2, f(g))} where g1 = f(g′1) and g2 = f(g′2).
But then g′1 and g
′
2 are adjacent to g in G. Since g1 and g2 are adjacent in G and f is
an automorphism, g′1 and g
′
2 are also adjacent. But then g, g
′
1, g
′
2 form a triangle in G,
a contradiction. Therefore no inner edge can be mapped to a connecting edge, so every
automorphism of G⊗f G respects the fundamental edge partition.
Lemma 3.20. Let G and H be graphs and let f : V (G) → V (H) be a function. Let {g, g′}
be an edge of G.
(i) If {g, g′} is not contained in any cycle of G, then the edge {(g, f(g′)), (g′, f(g))} is
not contained in any cycle of G⊗f H .
(ii) Let c be the length of the shortest cycle that contains {g, g′}. Then the shortest cycle
that contains the edge {(g, f(g′)), (g′, f(g))} in G⊗f H has length at least c.
(iii) Suppose that f is locally injective and let c be the length of the shortest cycle that
contains {g, g′}. Then the shortest cycle that contains the edge {(g, f(g′)), (g′, f(g))}
in G⊗f H has length at least 2c.
Proof. Let C be a cycle in G ⊗f H that contains {(g, f(g′)), (g′, f(g))}. Suppose that
{(g, f(g′)), (g′, f(g))}, {(g′, f(g1)), (g1, f(g′))}, . . . , {(gk, f(g)), (g, f(gk))} are the con-
necting edges in C in that order. Then gg′g1g2 . . . gkg is a cycle of length k in G that
contains the edge {g, g′}, so k ≥ c. Furthermore, if {g, g′} is not contained in any cycle
of G, then the edge {(g, f(g′)), (g′, f(g))} cannot be contained in any cycle of G ⊗f H .
Recall that if f is locally injective, any vertex of G ⊗f H is an endvertex of at most one
connecting edge by Lemma 2.8. Therefore, in this case the shortest cycle that contains
{(g, f(g′)), (g′, f(g))} has length at least 2c.
20 Ars Math. Contemp. 23 (2023) #P1.01
Theorem 3.21. Let G and H be connected graphs, let f : V (G) → V (H) be a function
and let the girth of G be equal to c. In any of the following cases, every automorphism of
G⊗f H respects the fundamental edge partition, i.e.
Ã(G,G, f) = Aut(G⊗f G).
(i) G is a tree and H is a bridgeless graph;
(ii) every edge of H is contained in a cycle of length at most c− 1;
(iii) the function f is locally injective and every edge of H is contained in a cycle of
length at most 2c− 1.
Proof. By Lemma 3.20, the shortest cycle that contains a connecting edge has length at
least c in case (ii), length at least 2c in case (iii) and is not contained in any cycle in case (i).
Since every inner edge is contained in a cycle in case (i), in a cycle of length at most c− 1
in case (ii), and in a cycle of length at most 2c − 1 in case (iii), a connecting edge cannot
be mapped to an inner edge by any automorphism.
3.3 Group of automorphisms of G ⊗f G
We now consider the group of automorphisms that respect the fundamental edge partition
in the special case when G = H and f : V (G) → V (G) is an automorphism. Since in this
case G ⊗f G is isomorphic to G ⊗ G, we could restrict ourselves to the case where f is
the identity. Note that in that case, the structure of the automorphism group was sketched
in the paper [8], but the proofs were never published.
Recall that by Corollary 3.7, every automorphism α of G has a lift, Ψ(α, f ◦ α ◦ f−1).
We call this automorphism the diagonal automorphism of G⊗f G corresponding to α, and
denote it by ᾱ. Denote by Ā(G, f) the set of all diagonal automorphisms. The following
proposition is straightforward to prove.
Proposition 3.22. The set Ā(G, f) is a subgroup of Ã(G,G, f), isomorphic to Aut(G).
To determine the structure of the group Ã(G,G, f), we first show that every element
of Ã(G,G, f) can be written as a product of an element from B̂(G,G, f) and an element
of Ā(G, f). Furthermore, we show that B̂(G,G, f) is a normal subgroup of Ã(G,G, f).
Proposition 3.23. Let G be a connected graph and let f : V (G) → V (G) be an automor-
phism. Let γ̃ be an automorphism of G⊗f G that preserves the fundamental edge partition.
Then there exist α ∈ Aut(G) and βg ∈ Aut(G)(f(N(g))) for every g ∈ V (G) such that
γ̃ = ᾱ
(∏
g∈V (G) Φ(g, βg)
)
.
Proof. Let α be the projection of γ̃ to Aut(G). Then ᾱ = Ψ(α, f ◦ α ◦ f−1) permutes the
copies gG in the right way, such as γ̃ does. Observe that ᾱ already agrees with γ̃ on the
endvertices of all the connecting edges. To obtain γ̃ from ᾱ, we only need to adjust, for
every g ∈ V (G), the action of ᾱ on the vertices from f(N(g)) that are not endvertices of
connecting edges. We can do this on every copy gG separately, by acting with Φ(g, βg),
where βg ∈ Aut(G) is induced by ᾱ−1γ̃. Also, βg ∈ Aut(G)(f(N(g))) since the vertices
from f(N(g)) have the right image already and are fixed by βg .
J. Kovič et al.: The Sierpiński product of graphs 21
Proposition 3.24. Let G be a connected graph and let f : V (G) → V (G) be an automor-
phism. Then the group B̂(G,G, f) is a normal subgroup of the group Ã(G,G, f).
Proof. Observe that the function λ : Ã(G,G, f) → Ā(G, f) defined by λ : Ψ(α,B) →
Ψ(α, f ◦α ◦ f−1) is a homomorphism of groups, with B̂(G,G, f) being its kernel. There-
fore, B̂(G,G, f) is a normal subgroup of Ã(G,G, f).
Theorem 3.25. Let G be a connected graph and let f : V (G) → V (G) be an automor-
phism. Then the group Ã(G,G, f) is a semidirect product,
Ã(G,G, f) = Ā(G, f)⋉ B̂(G,G, f).
Proof. The group B̂(G,G, f) is a normal subgroup of Ã(G,G, f) by Proposition 3.24. By
Proposition 3.23, every element of Ã(G,G, f) can be written as a product of a diagonal
automorphism and an element from B̂(G,G, f). Moreover, only the identity is in both
Ā(G, f) and B̂(G,G, f). This proves that Ã(G,G, f) is a semidirect product of Ā(G, f)
and B̂(G,G, f).
4 Sierpiński product with multiple factors
To form a Sierpiński product G3 ⊗f (G2 ⊗f1 G1) of graphs G3, G2 and G1, one needs
functions f1 : V (G2) → V (G1) and f : V (G3) → G2 ⊗f1 G1, which is rather imprac-
tical. Suppose a function f2 : V (G3) → V (G2) is given. Then a function f : V (G3) →
V (G2⊗f1G1) can be defined in a natural way as f(g) = (f2(g), f1(f2(g)) for g ∈ V (G3).
In other words, let φ : V (G2) → V (G2 ⊗f1 G1) be the function that maps every vertex
g ∈ V (G2) to the vertex (g, f1(g)) ∈ V (G2 ⊗f1 G1). Then f = φ ◦ f2. Now we can
define the Sierpiński product of the graphs G3, G2 and G1 with respect to f2 and f1 in the
following way:
G3 ⊗f2 G2 ⊗f1 G1 = G3 ⊗φ◦f2 (G2 ⊗f1 G1).
Note that with given functions f2 and f1, we cannot form this product in any other way,
therefore, the Sierpiński product is not associative.
In Figure 10 it is shown how the product C3⊗f2 C4⊗f1 C3 is formed in two steps (with
f1 : V (C4) → V (C3), f1 : i 7→ i (mod 3) and f2 : V (C3) → V (C4) being the identity
function on its domain).
It is now easy to see that Sierpiński products possess a nice recursive structure, similar
to Sierpiński graphs and generalized Sierpiński graphs. By the same reasoning as above,
the product Gm ⊗fm−1 · · · ⊗f2 G2 ⊗f1 G1, where V (Gℓ) = {0, 1, . . . , |Gℓ| − 1}, and
fℓ : V (Gℓ+1) → V (Gℓ), ℓ = 1, . . . ,m − 1, are arbitrary functions, can be constructed as
follows.
• First, take |G2| copies of the graph G1 and label them iG1, i ∈ {0, . . . , |G2| − 1}.
Vertices of these graphs have labels of form g2g1, where g2 ∈ V (G2) and g1 ∈
V (G1).
• Connect any two copies iG1 and jG1 if there is an edge {i, j} in G2. More precisely,
if {i, j} ∈ E(G2), we add an edge {if1(j), jf1(i)} between iG1 and jG1. The
resulting graph is then indeed the Sierpiński product G2 ⊗f1 G1.
22 Ars Math. Contemp. 23 (2023) #P1.01
⊗f1 =
0
1 2
3
G2 = C4
0
1 2
G1 = C3
00
01
02
10
12
11 22
21
20
30
32
31
K
⊗φ◦f2 K =
0
1 2
G3 = C3
000
011 022
100
111 122
200
211 222
Figure 10: Construction of the graph C3 ⊗f2 C4 ⊗f1 C3, where f1 : i 7→ i (mod 3) and
f2 = id.
• Next, we form the Sierpiński product of the graphs G3 and K(2) := G2 ⊗f1 G1.
To do so we take |G3| copies of the graph K(2), label them iK(2), i ∈ {0, . . . ,
|G3| − 1}, and connect iK(2) and jK(2) whenever {i, j} is an edge in G3. Such an
edge then has the form {if2(j)f1(f2(j)), jf2(i)f1(f2(i))}.
• The final step is to form the Sierpiński product of the graphs Gm and K(m − 1) in
the same way as we formed all the products so far: make |Gm| copies of K(m− 1)
and label them iK(m−1); then for every edge {i, j} in Gm we add an edge between
copies iK(m− 1) and jK(m− 1). Such an edge has then the following form
{ifm−1(j) . . . f1(f2 . . . (fm−1(j)) . . . ) , jfm−1(i) . . . f1(f2 . . . (fm−1(i)) . . . )}.
J. Kovič et al.: The Sierpiński product of graphs 23
The resulting graph is the product Gm ⊗fm−1 · · · ⊗f2 G2 ⊗f1 G1.
If G1 = · · · = Gm = G and functions f1, . . . , fm−1 are all the identity function, then
Gm ⊗fm−1 · · · ⊗f2 G2 ⊗f1 G1 is the generalized Sierpiński graph SnG; see also [8].
We can calculate the order and the size of the Sierpiński product of multiple factors
directly from the above construction.
Proposition 4.1. Let m ≥ 2, and let G1, . . . , Gm be arbitrary graphs. Further, let
f1 : V (G2) → V (G1), . . . , fm−1 : V (Gm) → V (Gm−1) be arbitrary functions. Then
the order and the size of the Sierpiński product Gm ⊗fm−1 · · · ⊗f1 G1 are as follows
|Gm ⊗fm−1 · · · ⊗f1 G1| =
m∏
ℓ=1
|Gℓ| ,
||Gm ⊗fm−1 · · · ⊗f1 G1|| =
m∑
ℓ=1
 m∏
j=ℓ+1
|Gj |
 ||Gℓ|| .
Note that neither the order nor the size of the Sierpiński product depends on the func-
tions fℓ. It would also be interesting to study some properties of the Sierpiński product
with multiple factors, such as diameter and girth.
5 Conclusion
This paper generalizes Sierpiński graphs even further than generalized Sierpiński graphs,
where the whole structure is based only on one graph. Here we create a product-like struc-
ture of two (or more) factors. Some basic graph theoretical properties are studied in detail,
and planar Sierpiński products are completely characterized. Apart from this, the symme-
tries of Sierpiński products are studied as well. In general, these are not fully understood.
In several cases we are able to determine the automorphism group of the Sierpiński product
of two graphs exactly.
In [14] an algorithm is given for recognizing generalized Sierpiński graphs. Given a
graph it is also natural to ask whether it can be represented as a Sierpiński product of
two or more graphs. Moreover, one can ask if such a representation is unique. The latter
question has a negative answer. Consider the Sierpiński product of C4 and 2K3 + e with
function f as in Figure 9. It can be easily verified that it is isomorphic to C8 ⊗f ′ K3
where f ′ : V (C8) → V (K3) is defined by f ′(1) = f ′(2) = f ′(5) = f ′(6) = 1 and
f ′(3) = f ′(4) = f ′(7) = f ′(8) = 2. However, in this case not all the factors are prime
with respect to the Sierpiński product: C8 can be represented as a Sierpiński product of C4
and K2 while 2K3 + e can be represented as a Sierpiński product of K2 and K3. It would
be interesting to see whether there exist prime graphs with respect to the Sierpiński product
G,H,G′, H ′ and functions f : V (G) → V (H), f ′ : V (G′) → V (H ′) such that G,H are
not isomorphic to G′, H ′ while G⊗f H is isomorphic to G′ ⊗f ′ H ′.
The Sierpiński product can also be defined in a similar way for graphs with loops
and multiple edges. In this case, a loop in G, say {g, g}, would correspond to a loop
{(g, f(g)), (g, f(g))} in G ⊗f H and a multiple edge in G would correspond to a multi-
ple edge in G ⊗f H . Finally, as with other products, one could also study the Sierpiński
product of infinite graphs.
24 Ars Math. Contemp. 23 (2023) #P1.01
ORCID iDs
Jurij Kovič https://orcid.org/0000-0003-0567-2626
Tomaž Pisanski https://orcid.org/0000-0002-1257-5376
Sara Sabrina Zemljič https://orcid.org/0000-0003-4026-0854
Arjana Žitnik https://orcid.org/0000-0001-7737-1836
References
[1] B. Alspach and E. Dobson, On automorphism groups of graph truncations, Ars Math.
Contemp. 8 (2015), 215–223, doi:10.26493/1855-3974.665.4b6, http://doi.org/10.
26493/1855-3974.665.4b6.
[2] M. Boben, R. Jajcay and T. Pisanski, Generalized cages, Electron. J. Comb. 22 (2015), research
paper p1.77, 19, doi:10.37236/4680, http://doi.org/10.37236/4680.
[3] G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. Henri Poincaré, Nouv. Sér.,
Sect. B 3 (1967), 433–438.
[4] E. Eiben, R. Jajcay and P. Šparl, Symmetry properties of generalized graph truncations, J.
Comb. Theory, Ser. B 137 (2019), 291–315, doi:10.1016/j.jctb.2019.01.002, http://doi.
org/10.1016/j.jctb.2019.01.002.
[5] A. Estrada-Moreno, E. D. Rodriguez-Bazan and J. A. Rodriguez-Velazquez, On distances
in generalized Sierpiński graphs, Appl. Anal. Discrete Math. 12 (2018), 49–69, doi:10.2298/
aadm160802001e, http://doi.org/10.2298/aadm160802001e.
[6] G. Exoo and R. Jajcay, Recursive constructions of small regular graphs of given degree and
girth, Discrete Math. 312 (2012), 2612–2619, doi:10.1016/j.disc.2011.10.021, http://doi.
org/10.1016/j.disc.2011.10.021.
[7] J. Geetha and K. Somasundaram, Total coloring for generalized Sierpiński graphs, Australas.
J. Comb. 63 (2015), 58–69, https://ajc.maths.uq.edu.au/pdf/63/ajc_v63_
p058.pdf.
[8] S. Gravier, M. K. se and A. Parreau, Generalized Sierpiński graphs, in: Posters at
EuroComb’11, Budapest Https://www.renyi.hu/conferences/ec11/posters/
parreau.pdf.
[9] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Discrete Math. Appl.
(Boca Raton), CRC Press, Boca Raton, FL, 2nd edition, 2011, doi:10.1201/b10959, http:
//doi.org/10.1201/b10959.
[10] A. M. Hinz, S. Klavžar and C. Petr, The Tower of Hanoi – Myths and Maths, Birkhäuser,
Cham, 2nd edition, 2018, doi:10.1007/978-3-319-73779-9, http://doi.org/10.1007/
978-3-319-73779-9.
[11] A. M. Hinz, S. Klavžar and S. S. Zemljič, Sierpiński graphs as spanning subgraphs of Hanoi
graphs, Cent. Eur. J. Math. 11 (2013), 1153–1157, doi:10.2478/s11533-013-0227-7, http:
//doi.org/10.2478/s11533-013-0227-7.
[12] A. M. Hinz, S. Klavžar and S. S. Zemljič, A survey and classification of Sierpiński-type graphs,
Discrete Appl. Math. 217 (2017), 565–600, doi:10.1016/j.dam.2016.09.024, http://doi.
org/10.1016/j.dam.2016.09.024.
[13] C.-H. Huang, J.-F. Fang and C.-Y. Yang, Edge-disjoint Hamiltonian cycles of WK-recursive
networks, in: J. Dongarra, K. Madsen and J. Waśniewski (eds.), Applied Parallel Computing.
State of the Art in Scientific Computing, Springer Berlin Heidelberg, Berlin, Heidelberg, 2006
pp. 1099–1104, doi:10.1007/11558958 132, http://doi.org/10.1007/11558958_
132.
J. Kovič et al.: The Sierpiński product of graphs 25
[14] W. Imrich and I. Peterin, Recognizing generalized Sierpiński graphs, Appl. Anal. Discrete
Math. 14 (2020), 122–137, doi:10.2298/aadm180331003i, http://doi.org/10.2298/
aadm180331003i.
[15] M. Jakovac and S. Klavžar, Vertex-, edge-, and total-colorings of Sierpiński-like graphs, Dis-
crete Math. 309 (2009), 1548–1556, doi:10.1016/j.disc.2008.02.026, http://doi.org/
10.1016/j.disc.2008.02.026.
[16] S. Klavžar and U. Milutinović, Graphs S(n, k) and a variant of the Tower of Hanoi problem,
Czech. Math. J. 47 (1997), 95–104, doi:10.1023/a:1022444205860, http://doi.org/10.
1023/a:1022444205860.
[17] S. Klavžar, U. Milutinović and C. Petr, 1-perfect codes in Sierpiński graphs., Bull. Aust.
Math. Soc. 66 (2002), 369–384, doi:10.1017/s0004972700040235, http://doi.org/10.
1017/s0004972700040235.
[18] S. Klavžar and S. S. Zemljič, On distances in Sierpiński graphs: almost-extreme vertices and
metric dimension, Appl. Anal. Discrete Math. 7 (2013), 72–82, doi:10.2298/aadm130109001k,
http://doi.org/10.2298/aadm130109001k.
[19] S. Klavžar and S. S. Zemljič, Connectivity and some other properties of generalized Sierpiński
graphs, Appl. Anal. Discrete Math. 12 (2018), 401–412, doi:10.2298/aadm170206009k,
http://doi.org/10.2298/aadm170206009k.
[20] A. Malnič, T. Pisanski and A. Žitnik, The clone cover, Ars Math. Contemp. 8 (2015), 95–
113, doi:10.26493/1855-3974.513.cbb, http://doi.org/10.26493/1855-3974.
513.cbb.
[21] B. Mohar and C. Thomassen, Graphs on surfaces, Johns Hopkins University Press, 2001.
[22] D. Parisse, On some metric properties of the Sierpiński graphs S(n, k), Ars Comb. 90 (2009),
145–160.
[23] T. Pisanski and T. W. Tucker, Growth in repeated truncation of maps, Atti Semin. Mat. Fis.
Univ. Modena 49 (2001), 167–176.
[24] J. A. Rodrı́guez-Velázquez, E. D. Rodrı́guez-Bazan and A. Estrada-Moreno, On generalized
Sierpiński graphs, Discuss. Math., Graph Theory 37 (2017), 547–560, doi:10.7151/dmgt.1945,
http://doi.org/10.7151/dmgt.1945.
[25] J. A. Rodrı́guez-Velázquez and J. Tomás-Andreu, On the Randić index of polymeric net-
works modelled by generalized Sierpiński graphs, MATCH Commun. Math. Comput. Chem.
74 (2015), 145–160, https://match.pmf.kg.ac.rs/electronic_versions/
Match74/n1/match74n1_145-160.pdf.
[26] B. Xue, L. Zuo and G. Li, The hamiltonicity and path t-coloring of Sierpiński-like graphs, Dis-
crete Appl. Math. 160 (2012), 1822–1836, doi:10.1016/j.dam.2012.03.022, http://doi.
org/10.1016/j.dam.2012.03.022.
[27] B. Xue, L. Zuo, G. Wang and G. Li, Shortest paths in Sierpiński graphs, Discrete Appl. Math.
162 (2014), 314–321, doi:10.1016/j.dam.2013.08.029, http://doi.org/10.1016/j.
dam.2013.08.029.