ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 171–186
https://doi.org/10.26493/1855-3974.2199.97e
(Also available at http://amc-journal.eu)
Some algebraic properties of
Sierpiński-type graphs*
Mohammad Farrokhi Derakhshandeh Ghouchan
Department of Mathematics, Institute for Advanced Studies in Basic Sciences (IASBS),
and the Center for Research in Basic Sciences and Contemporary Technologies, IASBS,
P. O. Box 45137-66731, Zanjan, Iran
Ebrahim Ghorbani †
Department of Mathematics, K. N. Toosi University of Technology,
P. O. Box 16765-3381, Tehran, Iran
Hamid Reza Maimani , Farhad Rahimi Mahid
Department of Basic Sciences, Shahid Rajaee Teacher Training University,
P. O. Box 16783-163, Tehran, Iran
Received 16 December 2019, accepted 4 November 2020, published online 21 October 2021
Abstract
This paper deals with some algebraic properties of Sierpiński graphs and a family of
regular generalized Sierpiński graphs. For the family of regular generalized Sierpiński
graphs, we obtain their spectrum and characterize those graphs that are Cayley graphs. As
a by-product, a new family of non-Cayley vertex-transitive graphs, and consequently, a
new set of non-Cayley numbers are introduced. We also obtain the Laplacian spectrum of
Sierpiński graphs in some particular cases, and make a conjecture on the general case.
Keywords: Sierpiński graph, spectrum, Laplacian, Cayley graph, non-Cayley number.
Math. Subj. Class. (2020): 05C50, 05C25, 05C75
*The authors would like to thank anonymous referees for constructive comments which led to improvement of
the presentation of the paper. The second author carried this work during a Humboldt Research Fellowship at the
University of Hamburg. He thanks the Alexander von Humboldt-Stiftung for financial support.
†Corresponding author.
E-mail addresses: farrokhi@iasbs.ac.ir, m.farrokhi.d.g@gmail.com (Mohammad Farrokhi Derakhshandeh
Ghouchan), ghorbani@kntu.ac.ir (Ebrahim Ghorbani), maimani@ipm.ir (Hamid Reza Maimani),
farhad.rahimi@sru.ac.ir (Farhad Rahimi Mahid)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
172 Ars Math. Contemp. 20 (2021) 171–186
1 Introduction
Sierpiński-type graphs show up in a wide range of areas; for instance, physics, dynamical
systems, probability, and topology, to name a few. The Sierpiński gasket graphs form one
of the most significant families of such graphs that are obtained by a finite number of
iterations that give the Sierpiński gasket in the limit. Several more families of Sierpiński-
type graphs have been introduced and studied in the literature (see Barrière, Comellas, and
Dalfó [1] and Hinz, Klavžar, and Zemljič [6]). In this paper, we deal with two families of
them, as described below.
For positive integers n, k, the Sierpiński graph S(n, k) is defined with vertex set [k]n,
where [k] := {1, . . . , k}, and two different vertices (u1, . . . , un) and (v1, . . . , vn) are ad-
jacent if and only if there exists a t ∈ [n] such that
• ui = vi for i = 1, . . . , t− 1,
• ut ̸= vt,
• uj = vt and vj = ut for j = t+ 1, . . . , n.
For instance, the graphs S(3, 3) and S(2, 4) are depicted in Figure 1.
222 223 232 233 322 323 332 333
221 231 321 331
212 213 312 313
211 311
122
123 132
133
121 131
112 113
111
44 43 34 33
41
42 31
32
14
13 24
23
11
12 21
22
Figure 1: The Sierpiński graphs S(3, 3) (left) and S(2, 4) (right).
Sierpinśki graphs S(n, k) were introduced in Klavžar and Milutinović [8]. The graph
S(n, 3) is indeed isomorphic to the graph of the Tower of Hanoi with n disks. The graph
S(n, k) has kn − k vertices of degree k and k vertices of degree k − 1 that are (i, . . . , i)
for i ∈ [k]. These vertices are called the extreme vertices.
In addition to S(n, k), we consider a ‘regularization’ of them as another family of
Sierpiński-type graphs. The graphs S++(n, k), introduced in Klavžar and Mohar [9],
are defined as follows. The graph S++(1, k) is the complete graph Kk+1. For n ≥ 2,
S++(n, k) is the graph obtained from the disjoint union of k + 1 copies of S(n− 1, k) in
which the extreme vertices in distinct copies of S(n− 1, k) are connected as the complete
graph Kk+1. See Figure 2 for an illustration of S++(3, 3).
Many properties of Sierpiński-type graphs, including those of S(n, k) and S++(n, k),
have been studied in the literature, for a survey see Hinz, Klavžar, and Zemljič [6]. In
M. Farrokhi D. G. et al.: Some algebraic properties of Sierpiński-type graphs 173
Figure 2: The graph S++(3, 3).
this paper, we investigate some algebraic properties of the two families of graphs, namely
the spectrum and the property of being a Cayley graph. More precisely, in Section 2,
we determine the spectrum of the graphs S++(n, k). The Laplacian spectrum of S(n, k)
is already known for k = 2, 3. We establish the case n = 2, in Section 3, and make
a conjecture on the Laplacian spectrum of S(n, k) in general. We also characterize the
graphs S++(n, k) that are Cayley graphs in Section 4. As a by-product, a new family of
non-Calyley vertex-transitive graphs are obtained. From this result, we conclude a new set
of square-free non-Cayley numbers in Section 5, and we discuss its distribution.
2 Spectrum of S++(n, k)
Let Γ be a simple graph with vertex set V (Γ) = {v1, . . . , vn} and edge set E(Γ). Its
adjacency matrix A(Γ) = [aij ] is an n × n symmetric matrix with aij = 1 if vi and vj
are adjacent, and aij = 0 otherwise. The multi-set of the eigenvalues of A(Γ) is called the
spectrum of Γ.
In this section, we determine the spectrum of S++(n, k). As we will see, the recursive
structure of these Sierpiński-type graphs also shows up in their spectrum. We first recall
some basic facts.
The incidence matrix of a graph Γ is a 0-1 matrix X(Γ) = [xve], with rows indexed by
the vertices and columns indexed by the edges of Γ, where xve = 1 if the vertex v is an
endpoint of the edge e. For a graph Γ, L(Γ) denotes the line graph of Γ, in which V (L(Γ))
corresponds with E(Γ), and two vertices of L(Γ) are adjacent if and only if they have a
common vertex as edges of Γ. The subdivision graph S(Γ) of Γ is the graph obtained by
inserting a new vertex into every edge of Γ. It is easy to verify that
X(Γ)⊤X(Γ) = 2I +A(L(Γ)), (2.1)
and, moreover, if Γ is k-regular, then
X(Γ)X(Γ)⊤ = kI +A(Γ). (2.2)
174 Ars Math. Contemp. 20 (2021) 171–186
The following lemma gives a recursive relation for the graphs S++(n, k).
Lemma 2.1. The graph S++(n+ 1, k) is isomorphic to L(S(S++(n, k))).
Proof. Let k be fixed. The graph Γn := S++(n, k) can be obtained by the union of S(n, k)
and S(n − 1, k) by adding a matching between the extreme vertices of the two graphs. If
we consider {0} × [k]n−1 as the vertex set of S(n− 1, k) (to make them compatible with
the length n of the vertices of S(n, k)), then ({0} ∪ [k])× [k]n−1 is the vertex set of Γn. It
follows that any edge e = {u,v} of Γn is of one of the following types:
(1) u = (u1, . . . , ur, u, v, . . . , v), v = (u1, . . . , ur, v, u, . . . , u) for some r ≤ n− 2 and
u ̸= v;
(2) u = (u1, . . . , un−1, u), v = (u1, . . . , un−1, v) with u ̸= v;
(3) u = (0, u, . . . , u), v = (u, u, . . . , u).
Each e = {u,v} ∈ E(Γn) is divided into two new edges eu and ev in S(Γn), where we
assume that u ∈ eu and v ∈ ev. We define a map ψ : E(S(Γn)) → ({0} ∪ [k]) × [k]n
based on the type of e as follows:
(i) If e is of type (1) or (2), then ψ(eu) = (u, v) and ψ(ev) = (v, u);
(ii) If e is of type (3), then ψ(eu) = (u, u) and ψ(ev) = (v, u).
It is easily seen that ψ is a one-to-one map. We show that ψ is an isomorphism from
L(S(Γn)) to Γn+1. Let e and e′ be two edges that share a vertex x of S(Γn). If x =
(x1, . . . , xn) is an ‘old’ vertex of S(Γn), then ψ(e) = (x, y) and ψ(e′) = (x, z) for some
y ̸= z. Then, it is clear that ψ(e) and ψ(e′) are adjacent in Γn+1. If x is a ‘new’ vertex
of S(Γn), then from (i) and (ii), it is clear that ψ(e) and ψ(e′) are adjacent in Γn+1. This
shows that ψ is indeed a one-to-one homomorphism. As L(S(Γn)) and Γn+1 have the
same number of edges, it follows that ψ is an isomorphism.
We recall that if A is a non-singular square matrix, then∣∣∣∣A BC D
∣∣∣∣ = |A| · ∣∣D − CA−1B∣∣ , (2.3)
where | · | denotes the determinant of a matrix. Also, recall that if M is a p× q matrix, then
|xI −MM⊤| = xp−q|xI −M⊤M |. (2.4)
(Note that (2.4) might not be valid if p ≤ q and x = 0, but this has no effect in our argument
since two polynomials that agree in all but finitely many points, agree everywhere.)
Let
f(x) = x2 + (2− k)x− k, (2.5)
and let f j(x) denote the polynomial of degree 2j obtained by j times composition of f
with itself. As a convention, we let f0(x) = x.
We now give the main result of this section.
M. Farrokhi D. G. et al.: Some algebraic properties of Sierpiński-type graphs 175
Theorem 2.2. Let k be an integer and Pn(x) denote the characteristic polynomial of the
adjacency matrix of S++(n, k). Then, Pn satisfies the recursion relation
Pn(x) = (x(x+ 2))
kn−2((k2)−1) Pn−1(f(x)), n ≥ 2, (2.6)
with P1(x) = (x − k)(x + 1)k. Moreover, for n ≥ 2, the spectrum of S++(n, k) consists
of the following eigenvalues:
(i) k with multiplicity 1,
(ii) the zeros of fn−1(x) + 1 each with multiplicity k,
(iii) the zeros of f j(x) each with multiplicity kn−2−j
((
k
2
)
− 1
)
for j = 0, 1, . . . , n− 2,
(iv) the zeros of f j(x)+2 each with multiplicity kn−2−j
((
k
2
)
− 1
)
+1 for j = 0, 1, . . . ,
n− 2.
Proof. Let Γn := S++(n, k). Suppose that X and Y are the incidence matrices of Γn−1
and S(Γn−1), respectively. By Lemma 2.1, Γn is isomorphic to L(S(Γn−1)). It follows
that
Y Y ⊤ =
[
kIp X
X⊤ 2Iq
]
,
where the matrix is divided according to the partition of the vertices into p = kn−1+kn−2
‘old’ vertices of Γn−1 and q = 12 (k
n + kn−1) ‘new’ vertices (which have degree 2) added
to Γn−1 to obtain S(Γn−1). Therefore, from (2.3),∣∣xI − Y Y ⊤∣∣ = |(x− k)Ip| · ∣∣∣(x− 2)Iq −X⊤ ((x− k)Ip)−1X∣∣∣
= (x− k)p
∣∣∣∣(x− 2)Iq − 1x− kX⊤X
∣∣∣∣
= (x− k)p−q
∣∣(x− 2)(x− k)Iq −X⊤X∣∣
= (x− k)p−q((x− 2)(x− k))q−p
∣∣(x− 2)(x− k)Ip −XX⊤∣∣ (by (2.4))
= (x− 2)q−p |((x− 2)(x− k)− k)Ip −A(Γn−1)| (by (2.2))
= (x− 2)q−pPn−1((x− 2)(x− k)− k). (2.7)
On the other hand, by (2.1) and (2.2), we have
Pn(x) =
∣∣(x+ 2)I2q − Y ⊤Y ∣∣ = (x+ 2)q−p ∣∣(x+ 2)Ip+q − Y Y ⊤∣∣ .
Now, from (2.7) it follows that
Pn(x) = (x(x+ 2))
q−pPn−1(x(x+ 2− k)− k),
implying (2.6).
To prove the second part of the theorem, note that as Γ1 = Kk+1, we have P1(x) =
(x− k)(x+ 1)k. From (2.6), we conclude that
P2(x) = (x(x+ 2))
(k2)−1(f(x)− k)(f(x) + 1)k,
176 Ars Math. Contemp. 20 (2021) 171–186
and since
f(x)− k = (x+ 2)(x− k), (2.8)
the assertion follows for n = 2. Now assume that n ≥ 3 and the assertion holds for n− 1.
So, we have
Pn−1(x) = (x− k)
(
fn−2(x) + 1
)k n−3∏
j=0
(
f j(x)
)mn−3−j (
f j(x) + 2
)1+mn−3−j
,
in which mi = ki
((
k
2
)
− 1
)
. It follows that
Pn−1(f(x)) = (f(x)− k)
(
fn−1(x) + 1
)k n−2∏
j=1
(
f j(x)
)mn−2−j (
f j(x) + 2
)1+mn−2−j
.
This, together with (2.6) and (2.8), implies the result.
Remark 2.3. It is straightforward to see that the zeros of f j(x) and f j(x) + 2 for j = 1
are 12 (k − 2 ±
√
k2 + 4) and 12 (k − 2 ±
√
k2 − 4), respectively, and for j ≥ 2 are of the
form
1
2
(k − 2)± 1
2
√
k(k + 2)± 2
√
k(k + 2)± 2
√
· · · ± 2
√
k2 + 4
and
1
2
(k − 2)± 1
2
√
k(k + 2)± 2
√
k(k + 2)± 2
√
· · · ± 2
√
k2 − 4,
respectively, each of them consisting of j nested radicals in iterative forms. Moreover, the
zeros of fn−1(x) + 1 are
− 1, k − 1, 1
2
(k − 2)± 1
2
√
k2 + 4k,
1
2
(k − 2)± 1
2
√
k(k + 2)± 2
√
k2 + 4k, . . . ,
1
2
(k − 2)± 1
2
√
k(k + 2)± 2
√
k(k + 2)± 2
√
· · · ± 2
√
k2 + 4k,
where the last one consists of n− 2 nested radicals.
3 Laplacian spectrum of S(n, k)
For a graph Γ, the matrix L(Γ) = D(Γ)−A(Γ) is the Laplacian matrix of Γ, where D(Γ)
is the diagonal matrix of vertex degrees. The multi-set of eigenvalues of L(Γ) is called the
Laplacian spectrum of Γ. In this section, we deal with the Laplacian spectrum of S(n, k).
This is trivial for n = 1 or k = 1. For k = 2, 3, the Laplacian spectrum of S(n, k) is
already known (see Remark 3.4 below). We establish the case n = 2, and put forward a
conjecture explicitly describing the Laplacian spectrum of S(n, k) in general.
Let Eij be a k × k matrix in which all entries are 0, except the (i, j) entry that is 1.
Consider the k2 × k2 matrix
C :=
k∑
i=1
k∑
j=1
(Eij ⊗ Eji),
M. Farrokhi D. G. et al.: Some algebraic properties of Sierpiński-type graphs 177
where ‘⊗’ denotes the Kronecker product. The matrix C is called the commutation matrix.
The main property of the commutation matrix (see Magnus and Neudecker [10]) is that it
commutes the Kronecker product: for any k × k matrices M,N ,
C(M ⊗N)C = N ⊗M.
Note that each row and each column of C corresponds with a pair (i, j) for 1 ≤ i, j ≤ k.
Moreover, C is indeed a permutation matrix in which the only 1 entry in the row (i, j) is
located at the column (j, i) for every 1 ≤ i, j ≤ k.
For n = 1, the Laplacian spectrum of S(1, k) = Kk is
{
0[1], k[k−1]
}
, where the
superscripts indicate multiplicities. In the following theorem, we determine the Laplacian
spectrum of S(2, k).
Theorem 3.1. The Laplacian spectrum of S(2, k) is the following:{
0[1], k[(
k
2)], (k + 2)[(
k−1
2 )],
(
1
2
(k + 2)± 1
2
√
k2 + 4
)[k−1]}
.
Proof. First, note that the graph S(2, k) consists of k copies ofKk together with a matching
M of size
(
k
2
)
; exactly one edge for each pair of copies of Kk. Let L denote the Laplacian
matrix of S(2, k), and L′ be the Laplacian matrix of the induced subgraph by the edges of
M . It is seen that L = Q − B, where Q = L(kKk) + I and B = I − L′. Note that B is
a permutation matrix with
(
k
2
)
+ k eigenvalues 1 and
(
k
2
)
eigenvalues −1. Observe that Q
has k eigenvalues 1 and k2 − k eigenvalues k + 1. We have the following bounds on the
dimensions of intersections of the eigenspaces of B and Q:
dim(E1(B) ∩ Ek+1(Q)) ≥ k2 − k +
(
k
2
)
+ k − k2 =
(
k
2
)
,
dim(E−1(B) ∩ Ek+1(Q)) ≥ k2 − k +
(
k
2
)
− k2 =
(
k
2
)
− k,
in which Eλ denotes the eigenspace corresponding to the eigenvalue λ. For x ∈ E1(B) ∩
Ek+1(Q), we have Lx = kx and for x ∈ E−1(B)∩Ek+1(Q), Lx = (k+2)x. This means
that L has eigenvalues k and k+2 with multiplicities at least
(
k
2
)
and
(
k
2
)
−k, respectively.
We also have
Q = Ik ⊗ ((k + 1)Ik − Jk), (3.1)
and from the eigenvalues of Q,
Q2 − (k + 2)Q+ (k + 1)I = O. (3.2)
Coming back to B, for each of the extreme vertices (1, 1), . . . , (k, k) of S(2, k), there is a
1 on all the entries of the diagonal of B. The off-diagonal 1’s correspond with the edges
of M . By the definition of S(2, k), the edges of M connect the vertices (i, j) and (j, i) for
i ̸= j. It turns out that B is the commutation matrix, and thus
BQB = ((k + 1)Ik − Jk)⊗ Ik. (3.3)
The right sides of (3.1) and (3.3) commute, and so
BQBQ = QBQB.
178 Ars Math. Contemp. 20 (2021) 171–186
Next, we see that
(L2 − (k + 2)L+ kI)(QB −BQ)
= ((Q−B)2 − (k + 2)(Q−B) + kI)(QB −BQ)
=
(
Q2 − (k + 2)Q+ kI +B2 + (k + 2)B −QB −BQ
)
(QB −BQ)
= ((k + 2)B −QB −BQ) (QB −BQ) (by (3.2) and since B2 = I)
= Q2 − (k + 2)Q−B
(
Q2 − (k + 2)Q
)
B − (QB)2 + (BQ)2
= (BQ)2 − (QB)2
= O.
The above equality shows that every vector in the column space of QB − BQ is an
eigenvector forLwith eigenvalue λ, where λ2−(k+2)λ+k = 0. To obtain the multiplicity
of such λ, we compute the rank of QB −BQ:
rank(QB −BQ) = rank(Q−BQB)
= rank(Ik ⊗ ((k + 1)Ik − Jk)− ((k + 1)Ik − Jk)⊗ Ik)
= rank(Jk ⊗ Ik − Ik ⊗ Jk)
= 2k − 2. (3.4)
To show (3.4), suppose P is a k × k matrix whose first column is 1√
k
(1, . . . , 1)⊤ and that
PP⊤ = Ik. Then, Jk = P (kE11)P⊤, and so
Jk ⊗ Ik − Ik ⊗ Jk = (P ⊗ P )
(
(kE11 ⊗ Ik)− (Ik ⊗ kE11)
)
(P⊤ ⊗ P⊤).
Since (kE11 ⊗ Ik) − (Ik ⊗ kE11) is a diagonal matrix having precisely 2k − 2 non-zero
entries in the columns 2, 3, . . . , k, k + 1, 2k + 1, 3k + 1, . . . , (k − 1)k + 1, (3.4) follows.
As x2 − (k + 2)x + k is an irreducible polynomial, each of its roots is an eigenvalue
of L with multiplicity at least k − 1. The matrix L has a 0 eigenvalue. Thus, we have
obtained so far
(
k
2
)
+
(
k
2
)
− k + 2(k − 1) + 1 = k2 − 1 eigenvalues of L. As the sum of
the eigenvalues of L is twice the number of edges of S(2, k), it follows that the remaining
eigenvalue is k + 2. So the proof is complete.
Based on empirical evidence, we put forward the following conjecture.
Conjecture 3.2. For n, k ≥ 2, the Laplacian spectrum of S(n, k) consists of the following
eigenvalues:
(i) 0 with multiplicity 1.
(ii) The zeros of f j(k − x), each with multiplicity 12 (k
n−j − 2kn−j−1 + k) for j =
0, 1, . . . , n− 1, where f is given in (2.5).
(iii) The zeros of f j(k − x) + 2, each with multiplicity 12 (k
n−j−1 − 1)(k − 2) for j =
0, 1, . . . , n− 2.
Remark 3.3. The zeros of f j(k−x) and f j(k−x)+2 for j = 1 are 12 (k+2±
√
k2 + 4)
and 12 (k + 2±
√
k2 − 4), respectively, and for j ≥ 2 are of the form
1
2
(k + 2)± 1
2
√
k(k + 2)± 2
√
k(k + 2)± 2
√
· · · ± 2
√
k2 + 4
M. Farrokhi D. G. et al.: Some algebraic properties of Sierpiński-type graphs 179
and
1
2
(k + 2)± 1
2
√
k(k + 2)± 2
√
k(k + 2)± 2
√
· · · ± 2
√
k2 − 4,
respectively, each of them consisting of j nested radicals.
Remark 3.4. The graph S(n, 2) is the path graph on 2n vertices. Proposition 3.5 below
shows that Conjecture 3.2 holds for S(n, 2). In Grigorchuk and Šunić [5], the spectrum
of the Schreier graph Γn was determined. The graph Γn is, in fact, the graph obtained
from S(n, 3) by adding a loop on each extreme vertex. By the way the adjacency matrix of
A(Γn) is defined in [5], for each loop a 1 entry on the diagonal is considered, so that each
row and column of A(Γn) has constant sum 3. It is then observed that the Laplacian spec-
trum of S(n, 3) can be deduced from the spectrum of Γn, which agrees with Conjecture 3.2.
In summary, Conjecture 3.2 holds for n = 2 and for k = 2, 3.
It is known in the literature that the characteristic polynomial of the Laplacian matrix
of a path can be expressed in terms of the Chebyshev polynomials. From this fact, for a
path with 2n vertices, we obtain the iterated form according to Conjecture 3.2. For the sake
of completeness, we give its complete argument here.
Proposition 3.5. The characteristic polynomial of the Laplacian matrix of the path graph
on 2n vertices is equal to x
∏n−1
j=0 g
j(2− x), where g(x) = x2 − 2.
Proof. Let ϕm be the characteristic polynomial of the Laplacian matrix of the path graph on
m vertices. Let Tm and Um be the Chebyshev polynomials of degree m of the first and the
second kind, respectively. Then Tm is the only polynomial satisfying Tm(cos θ) = cosmθ
and Um(x) = sin((m + 1) arccosx)/ sin(arccosx) (Snyder [18]). From the identities
given in Cvetković, Doob, and Sachs [2, p. 220], it follows that ϕm(x) = xUm−1(x/2−1).
By successive use of the identity U2k−1(x) = 2Tk(x)Uk−1(x) (see [18, p. 98]), we get
U2n−1(x) = 2
n−1T2n−1(x)T2n−2(x) · · ·T2(x)U1(x).
Note that U1(x) = 2x and T2(x) = 2x2 − 1. It is seen that 2T2(x/2 − 1) = x2 −
4x + 2 = g(2 − x). This, together with the identity T2k(x) = T2(Tk(x)), implies that
2T2j (x/2− 1) = gj(2− x). The proof is now complete.
4 What S++(n, k) are Cayley graphs?
Recall that a graph Γ is vertex-transitive if for any two vertices u, v of Γ, there exists an
automorphism σ of Γ such that σ(u) = v. Let G be a group and C ⊂ G such that 1 ̸∈ C
and c ∈ C implies that c−1 ∈ C. The Cayley graph Cay(G,C) with the group G and the
‘connection set’ C is the graph with vertex set G in which vertex u is connected to v if and
only if vu−1 ∈ C.
It is known that any Cayley graph is vertex-transitive. In the other way around, at least
for small orders, it seems that the great majority of vertex-transitive graphs are Cayley
graphs, see McKay and Praeger [12]. It is expected to continue to be this way for larger or-
ders. In fact, it is conjectured in Praeger, Li, and Niemeyer [15] that most vertex-transitive
graphs are Cayley graphs. In this section, we first determine what S++(n, k) are vertex-
transitive and, then, classify S++(n, k) that are Cayley graphs.
180 Ars Math. Contemp. 20 (2021) 171–186
Proposition 4.1. The graph S++(n, k) is vertex-transitive if and only if either n ≤ 2 or
k ≤ 2.
Proof. We have S++(n, 1) ∼= K2, S++(1, k) ∼= Kk+1, and S++(n, 2) is the cycle graph
on 2n−1 · 3 vertices, which are all vertex-transitive graphs. By Lemma 2.1, S++(2, k) is
isomorphic to L(S(Kk+1)). In the graph S(Kk+1), the ‘new’ vertices are in one-to-one
correspondence with 2-subsets of [k+1]. It is then easy to see that that any permutation of
[k+ 1] induces an automorphism of S(Kk+1). Now, for a given pair of edges of S(Kk+1)
which can be represented as e = {i, {i, j}} and e′ = {i′, {i′, j′}}, the automorphism
induced by a permutation σ that σ(i) = i′ and σ(j) = j′, maps e to e′. It follows that
S(Kk+1) is edge-transitive, and so L(S(Kk+1)) ∼= S++(2, k) is vertex-transitive. Hence,
assume that n ≥ 3 and k ≥ 3. We observe that an extreme vertex of a copy ∆ of S(n−1, k)
in Γ = S++(n, k) cannot be mapped to a non-extreme vertex of ∆ by any automorphism
of Γ. To be more precise, let u = (1, . . . , 1, 1) and v = (1, . . . , 1, 2). It can be seen that u
is a cut vertex for the induced subgraph by the vertices at distance at most 3 form u, while
v is not a cut vertex for the induced subgraph by the vertices at distance at most 3 form
v. It follows that u cannot be mapped to v by any automorphism of Γ, and thus Γ is not
vertex-transitive.
From Proposition 4.1, it follows that the graphs S++(n, k) for n ≥ 3 and k ≥ 3 cannot
be Cayley graphs. The graphs S++(n, 1), S++(n, 2), and S++(1, k) are all Cayley graphs.
It remains to characterize what S++(2, k) are Cayley graphs for k ≥ 3. This is our goal in
the rest of this section.
Definition 4.2. Let Γ be a graph and ∆ a subgraph of Γ. We say that Γ is strongly ∆-
partitioned if:
(i) The vertex set of Γ is partitioned by the vertex sets of copies ∆0, . . . ,∆k of ∆.
(ii) Apart from ∆0, . . . ,∆k, the graph Γ contains no further copies of ∆.
By the way S++(n, k) is defined, it is constructed based on k+1 copies of S(n−1, k).
The following proposition gives a structural property of S++(n, k) that it is indeed strongly
S(n − 1, k)-partitioned for n ≥ 2 and k ≥ 3. Note that this is not the case for k = 2
because S++(n, 2), that is a cycle with 3 · 2n−1 vertices, contains more than three copies
of S(n− 1, 2), which is a path on 2n−1 vertices. Although we only need the case n = 2 of
the proposition, we state it in its full generality because it could be of independent interest.
Proposition 4.3. Let n ≥ 2 and k ≥ 3. The graph S++(n, k) is strongly S(n − 1, k)-
partitioned.
Proof. Let Γ := S++(n, k) and Γ0, . . . ,Γk be the k + 1 copies of S(n − 1, k) used to
construct Γ by its definition. Clearly, V (Γ0), . . . , V (Γk) is a partition of V (Γ). We show
that Γ contains no more copies of S(n − 1, k). Let ∆ be a subgraph of Γ isomorphic to
S(n− 1, k).
First, assume that n = 2. Let u ∈ V (∆) ∩ V (Γt) for some t, with 0 ≤ t ≤ k.
Since u has at most one neighbor in V (Γ) \ V (Γt) and k ≥ 3, there exists another vertex
v ∈ V (∆)∩V (Γt) adjacent to u. Now, ifw is any vertex of ∆ other than u and v, then since
w is adjacent to two vertices u and v of Γt it must belong to V (Γt). Hence V (∆) ⊆ V (Γt)
and, consequently, ∆ = Γt.
M. Farrokhi D. G. et al.: Some algebraic properties of Sierpiński-type graphs 181
Now, let n ≥ 3. Note that S(n − 1, k) is connected and has no bridges since every
edge of S(n − 1, k) lies on a cycle (which can be seen by induction on n). If ∆ ̸= Γi
for i = 0, . . . , k, then ∆ shares its vertices with at least two Γs and Γt. By the definition,
exactly one extreme vertex, say u, of Γs is adjacent to exactly one extreme vertex, say v,
of Γt. Because of the connectivity, ∆ must contain the edge uv. Note that for any vertex w
outside Γs and Γt, the distance between w and either u or v is greater than the diameter of
S(n−1, k), and so w ̸∈ V (∆). It follows that ∆ is a subgraph of Γ′ := Γ[V (Γs)∪V (Γt)].
However, uv is a bridge for Γ′ and thus a bridge for ∆, a contradiction.
The following lemma reveals the structure of strongly ∆-partitioned Cayley graphs.
Lemma 4.4. Let Γ be a Cayley graph with a subgraph ∆ such that Γ is strongly ∆-
partitioned. Then, the vertex sets of the copies of ∆ are all the right cosets of a subgroup
of the underlying group of Γ.
Proof. Let Γ be a Cayley graph on a group G, and X ⊆ G be such that 1 ∈ X and Γ[X],
the subgraph of Γ induced by X , is isomorphic to ∆. Since for any x ∈ X , Γ[Xx−1]
is isomorphic to ∆ and 1 ∈ Xx−1, from the hypothesis of the lemma, it follows that
Xx−1 = X . Thus XX−1 = X and, hence, X is a subgroup of G. As for any g ∈ G,
Γ[Xg] is isomorphic to ∆ and the setsXg cover all elements ofG, it follows that the vertex
set of every induced subgraph of Γ isomorphic to ∆ is a right coset of X , as required.
Definition 4.5. Let Γ be a strongly ∆-partitioned graph. We say that Γ has connection
constant c if there are exactly c edges between any two copies of ∆ in Γ. We denote the set
of all strongly ∆-partitioned graphs with connection constant c by SPc(∆).
Remark 4.6. The family SP1(Kd) contains only one regular graph. However, this is not
the case in any regular graph ∆. If Γ ∈ SP1(∆) is a regular graph with ∆ being a d-
regular graph on k vertices, then Γ necessarily contains k + 1 copies of ∆ and thus Γ is
(d+1)-regular with k(k+1) vertices. For instance, in the case in which ∆ is C4, the cycle
on 4 vertices, Γ is a cubic graph on 20 vertices. By a computer search, we found all the
regular graphs in SP1(C4). It turned out that there are seven non-isomorphic such graphs,
among which only one is a Cayley graph.
Here we recall some notions from group theory that will be used in what follows. Let
G be a finite group and H be a nontrivial proper subgroup of G. The conjugate of H by
an element g of G is defined as Hg = {hg : h ∈ G}, where hg := g−1hg denotes the
conjugate of h by g. The group G is called a Frobenius group with Frobenius complement
H if H ∩ Hg = {1} for all g ∈ G \ H . A celebrated theorem of Frobenius states that
N := G \
⋃
g∈G(H \ {1})g is a normal subgroup of G, called the Frobenius kernel of G,
satisfying G = NH and N ∩H = {1}, that is, G = N ⋊H is a semidirect product of N
by H (see [17, 8.5.5]). The other concepts we use in the following are standard and can be
found in Robinson [17].
Theorem 4.7. Suppose that Γ and ∆ are two regular graphs and Γ ∈ SP1(∆). If Γ is a
Cayley graph Cay(G,C), then |∆|+1 = pm is a prime power, G = N ⋊H is a Frobenius
group with minimal normal Frobenius kernel N ∼= Zmp and Frobenius complement H ,
C = C ′ ∪ {c} with ∆ ∼= Cay(H,C ′) and c2 = 1, and either
(i) c ∈ N and H = ⟨C ′⟩, or
182 Ars Math. Contemp. 20 (2021) 171–186
(ii) c = hn for some h ∈ H \ {1} and n ∈ N \ {1}, and H = ⟨C ′, h⟩.
Conversely, if ∆ satisfies the above conditions, then Cay(G,C) ∈ SP1(∆).
Proof. Let Γ = Cay(G,C), and ∆0,∆1, . . . ,∆k be the copies of ∆ in Γ. As there is
exactly one edge between any two copies of ∆, it is observed that |∆| = k and Γ is (d+1)-
regular if ∆ is d-regular. Let H := V (∆0) and assume, without loss of generality, that
1 ∈ H . By Lemma 4.4, H is a subgroup of G. Let C ′ be the neighborhood of 1 in Γ[H].
Since Γ is (d + 1)-regular, besides the elements of C ′, the vertex 1 has exactly one other
neighbor, say c ∈ G \ H . So C = C ′ ∪ {c}. Since H is a subgroup of G, C ′−1 ⊆ H ,
which implies that C ′−1 = C ′. Thus, c = c−1 is an involution. Clearly, Hc ̸= H so that
Γ[Hc] = ∆i for some 1 ≤ i ≤ k. On the other hand,
1 = |E(∆0,∆i)| = |{{h, ch} : h ∈ H ∩Hc}| = |H ∩Hc|,
from which it follows that H ∩Hc = {1}. Now, a simple verification shows that Hch ∩
Hch′ = ∅ for all distinct elements h, h′ ∈ H . Since Γ[H] = ∆0 and Γ[Hch] (h ∈ H) are
equal to ∆1, . . . ,∆k in some order, we must have
G = H ∪
⋃
h∈H
Hch,
where the unions are disjoint. As a result, every element g ∈ G \ H can be written as
g = hch′ for some h, h′ ∈ H , from which it follows that
H ∩Hg = (Hh
′−1
∩ (Hh)c)h
′
= (H ∩Hc)h
′
= {1}h
′
= {1}.
Hence, G is a Frobenius group with complement H . Let N be the Frobenius kernel of G.
By [17, 10.5.1(i)], N is nilpotent. Let N0 be a nontrivial characteristic subgroup of N with
minimum order. Then N0 is a normal subgroup of G (see [17, 1.5.6(iii)]). Note that N0
is an elementary Abelian p-group for N0 is nilpotent and the subgroup of N0 generated
by central elements of a given prime order p dividing |Z(N0)| is a characteristic subgroup
of N0 and hence of N (see [17, 1.5.6(ii)]). If N ̸= N0, then N0H is a Frobenius group
for N0H is a subgroup of G and H ∩ Hg = 1 for all g ∈ N0H \ H . Moreover, as a
proper subgroup of N , |N0| ≤ |N |/2 ≤ (k + 1)/2 and hence |N0| − 1 is not divisible by
|H| = k contradicting [17, Exercises 8.5(6)]. Thus N = N0 so that k + 1 = |N | = pm
is a prime power for some m ≥ 1. Note that N is a minimal normal subgroup of G
for if N contains a nontrivial normal subgroup N0 of G properly, then N0H would be a
Frobenius group which leads us to the same contradiction as above. If c ∈ N , then since
G ⊆ N⟨C ′⟩ it follows that H = ⟨C ′⟩. Now assume that c /∈ N . Then cn ∈ H \ {1} for
some n ∈ N \ {1}. As G ⊆ N⟨C ′, cn⟩ it follows that H = ⟨C ′, cn⟩, as required. The
converse is straightforward.
We are now in a position to conclude the main result of this section.
Theorem 4.8. The graph S++(n, k) is a Cayley graph if and only if either
(i) n = 1,
(ii) k ≤ 2, or
M. Farrokhi D. G. et al.: Some algebraic properties of Sierpiński-type graphs 183
(iii) n = 2 and k + 1 = pm is a prime power.
Furthermore, in the case (iii), we have
S++(n, k) ∼= Cay(G, (H \ {1}) ∪ {c}),
for every Frobenius group G with complement H of order pm − 1, elementary Abelian
minimal normal Frobenius kernel of order pm, and involution c ∈ G \H .
Proof. By Proposition 4.1, S++(n, k) for n ≥ 3 and k ≥ 3 is not a Cayley graph. As
mentioned above, S++(n, 1), S++(n, 2), and S++(1, k) are all Cayley graphs. So, we
may assume that n = 2 and k ≥ 3.
First, we show that S++(2, q − 1) are Cayley graphs for all prime powers q. Let Fq
denote the finite field with q elements. Then G := F∗q ×Fq together with the multiplication
(x, a) · (y, b) = (xy, xb+ a),
forms a group known as one dimensional affine group. We show that S++(2, q − 1) ∼=
Cay(G,C), where C =
{
(x, 0) : 1 ̸= x ∈ F∗q
}
∪ {(−1,−1)}. To this end, let H :=
{(x, 0) : x ∈ F∗q} be a subgroup of G of order q − 1. Then H has q right cosets each
of which induces a complete subgraph in Cay(G,C) for h′g(hg)−1 = h′h−1 ∈ C for all
distinct elements hg and h′g of a right coset Hg of H . Since (x, 0)(1, ax−1) = (x, a)
covers all elements of G when x and a ranges over F∗q and Fq , respectively, it follows that
every right coset of H has a representative of the form (1, b) for some b ∈ Fq . Let Hg and
Hg′ be distinct right cosets of H with g = (1, a) and g′ = (1, a′). Then an element hg of
Hg is adjacent to an element h′g′ of Hg′ if and only if h′g′g−1h−1 = (h′g′)(hg)−1 ∈ C
or equivalently (h′g′)(hg)−1 = (−1,−1) as g′g−1 /∈ H . A simple verification shows that
this equation has a unique solution for (h, h′) so that there is a unique edge between any
two right cosets of H . Indeed, h = (x, 0) and h′ = (x′, 0) satisfy the equation if and only
if −x′ = x = (a′ − a)−1. Hence, from the definition, it follows that S++(2, q − 1) ∼=
Cay(G,C).
Now, assume that Γ := S++(2, k) ∼= Cay(G,C) be a presentation of S++(2, k) as a
Cayley graph. By Proposition 4.3, Γ is strongly Γ0-partitioned for some complete subgraph
Γ0 of Γ of order k. Let H := V (Γ0) and assume that 1 ∈ H . We know from Lemma 4.4
that H is a subgroup of G. By Theorem 4.7, k + 1 = pm is a prime power, G = N ⋊H
is a Frobenius group with Frobenius kernel N and Frobenius complement H such that
N ∼= Zmp is a minimal normal subgroup of G, C = C ′ ∪ {c}, C ′−1 = C ′ ⊆ H , c2 = 1,
and either
(a) c ∈ N and H = ⟨C ′⟩, or
(b) c = hn for some h ∈ H \ {1} and n ∈ N \ {1}, and H = ⟨C ′, h⟩.
Since Γ0 is a complete graph, we must have H \ {1} ⊆ C. Then, (a) and (b) together are
equivalent to say that c ∈ G \H . The proof is now complete.
As a generalization of Theorem 4.7, we pose the following problem.
Problem 4.9. Let ∆ be a regular graph. Classify all Cayley graphs in SPc(∆) for c ≥ 2.
184 Ars Math. Contemp. 20 (2021) 171–186
5 New non-Cayley numbers
In this final section, we give a partial answer to a famous rather old open problem in alge-
braic graph theory. A positive integer n is called a Cayley number if all vertex-transitive
graphs of order n are Cayley graphs. Marušič [11] in 1983 posed the problem of charac-
terizing the set NC of all non-Cayley numbers. Since disjoint unions of copies of vertex-
transitive (non-Cayley) graphs are again vertex-transitive (non-Cayley) graphs, it follows
that every multiple of a non-Cayley number is again a non-Cayley number. Hence the
problem of determining NC reduces to finding ‘minimal’ non-Cayley numbers. It is well-
known that all primes are Cayley numbers. Following a series of papers by various authors,
McKay and Praeger [13] and Iranmanesh and Praeger [7] provided necessary and sufficient
conditions under which the product of two and three distinct primes is a Cayley number,
respectively. In the same paper, McKay and Praeger established the following remarkable
result determining all non-square-free Cayley numbers.
Theorem 5.1 (McKay and Praeger [13]). Let n be a positive integer that is divisible by the
square of a prime p. Then n ∈ NC unless n = p2, n = p3, or n = 12.
It follows that, for determining NC, it is enough to consider only square-free positive
integers. While the problem is yet open for the products of at least four distinct primes,
there are partial results worth to mention here.
Theorem 5.2 (Dobson and Spiga [3]). There exists an infinite set of primes every finite
product of its distinct elements is a Cayley number.
As a consequence of Theorem 4.8, the graph S++(2, k) that has k(k + 1) vertices is
not a Cayley graph if k + 1 is not a prime power. Therefore, we obtain a new infinite class
of square-free non-Cayley numbers as follows.
Theorem 5.3. Let k be any positive integer such that k(k+ 1) is square-free, and k+ 1 is
not a prime. Then, k(k + 1) ∈ NC.
As mentioned in Dobson and Spiga [3], it is straightforward by making use of the
group-theoretic and the number-theoretic results already available in the literature to prove
that Cayley numbers have density zero in the set of natural numbers, and hence the density
of non-Cayley numbers is 1. In the light of this fact, one might wonder about the dis-
tribution of the numbers k satisfying the conditions of Theorem 5.3 in the set of positive
integers. The following theorem shows that for large enough N , more than one third of
positive integers less than or equal to N satisfies the conditions of Theorem 5.3.
Theorem 5.4. The density of the set
{k : k(k + 1) is square-free, and k + 1 is not a prime}
is about 0.3226.
Proof. Let f ∈ Z[t] be a primitive polynomial (that is, the greatest common divisor of
its coefficients is 1) without multiple roots such that its image on N has k-free greatest
common divisor. Recall that a number that is not divisible by any proper k-th power is
called k-free. Let Skf (x) denote the number of all positive integers n ≤ x such that f(n) is
k-free, and consider
δf,k :=
∏
p prime
(
1− ϱ(p
k)
pk
)
,
M. Farrokhi D. G. et al.: Some algebraic properties of Sierpiński-type graphs 185
where ϱ(d) denotes the number of roots of f in Zd. Ricci [16] (see also Pappalardi [14])
proved that
Skf (x) ∼ δf,kx
provided that deg f ≤ k. Clearly, the function f(t) := t(t + 1) satisfies the above re-
quirements of Ricci’s theorem for k = 2. Also, it is obvious that ϱ(p2) = 2 for all primes
p. Thus, by Ricci’s theorem, the density of all positive integers k, for which k(k + 1) is
square-free, in the set of all positive integers, is equal to
δf,2 =
∏
p prime
(
1− 2
p2
)
= 2CFeller-Tornier − 1 ≈ 0.3226340989,
where CFeller-Tornier is the Feller-Tornier constant (see Finch [4, §2.4.1]). Since primes have
zero density in the set of all positive integers, the result follows.
To date, all the numbers whose membership in NC is known are determined based on
the results of [7, 12, 13]. Using a computer search, we see that the list of the numbers
whose membership in NC is not yet determined begins with
9982, 12958, 18998, 19646, 20398, 21574, 24662, 25438, 25606, . . . .
A simple computation reveals that among the numbers less than or equal to 108, there
are 2763 square-free integers of the form k(k + 1), with k + 1 not a prime of which the
following eight integers are new non-Cayley numbers:
1386506, 2668322, 15503906, 23985506, 38359442, 74261306, 89898842, 95912642.
ORCID iDs
Mohammad Farrokhi Derakhshandeh Ghouchan https://orcid.org/0000-0002-5850-969X
Ebrahim Ghorbani https://orcid.org/0000-0001-7195-8601
Hamid Reza Maimani https://orcid.org/0000-0001-9020-0871
Farhad Rahimi Mahid https://orcid.org/0000-0001-8996-2078
References
[1] L. Barrière, F. Comellas and C. Dalfó, Fractality and the small-world effect in Sierpinski
graphs, J. Phys. A 39 (2006), 11739–11753, doi:10.1088/0305-4470/39/38/003.
[2] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications, Johann
Ambrosius Barth, Heidelberg, 3rd edition, 1995.
[3] T. Dobson and P. Spiga, Cayley numbers with arbitrarily many distinct prime factors, J. Comb.
Theory Ser. B 122 (2017), 301–310, doi:10.1016/j.jctb.2016.06.005.
[4] S. R. Finch, Mathematical Constants, volume 94 of Encyclopedia of Mathematics and its Ap-
plications, Cambridge University Press, Cambridge, 2003.
[5] R. Grigorchuk and Z. Šunić, Schreier spectrum of the Hanoi Towers group on three pegs, in:
P. Exner, J. P. Keating, P. Kuchment, T. Sunada and A. Teplyaev (eds.), Analysis on Graphs and
Its Applications, American Mathematical Society, Providence, RI, volume 77 of Proceedings
of Symposia in Pure Mathematics, pp. 183–198, 2008, doi:10.1090/pspum/077/2459869.
[6] 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.
186 Ars Math. Contemp. 20 (2021) 171–186
[7] M. A. Iranmanesh and C. E. Praeger, On non-Cayley vertex-transitive graphs of order a product
of three primes, J. Comb. Theory Ser. B 81 (2001), 1–19, doi:10.1006/jctb.2000.1985.
[8] S. Klavžar and U. Milutinović, Graphs S(n, k) and a variant of the Tower of Hanoi problem,
Czechoslovak Math. J. 47 (1997), 95–104, doi:10.1023/a:1022444205860.
[9] S. Klavžar and B. Mohar, Crossing numbers of Sierpiński-like graphs, J. Graph Theory 50
(2005), 186–198, doi:10.1002/jgt.20107.
[10] J. R. Magnus and H. Neudecker, The commutation matrix: some properties and applications,
Ann. Statist. 7 (1979), 381–394.
[11] D. Marušič, Cayley properties of vertex symmetric graphs, Ars Combin. 16 (1983), 297–302.
[12] B. D. McKay and C. E. Praeger, Vertex-transitive graphs which are not Cayley graphs, I, J.
Austral. Math. Soc. Ser. A 56 (1994), 53–63, doi:10.1017/s144678870003473x.
[13] B. D. McKay and C. E. Praeger, Vertex-transitive graphs that are not Cayley graphs, II, J.
Graph Theory 22 (1996), 321–334, doi:10.1002/(sici)1097-0118(199608)22:4⟨321::aid-jgt6⟩
3.3.co;2-9.
[14] F. Pappalardi, A survey on k-freeness, in: S. D. Adhikari, R. Balasubramanian and K. Srinivas
(eds.), Number Theory, Ramanujan Mathematical Society, Mysore, volume 1 of Ramanujan
Mathematical Society Lecture Notes Series, pp. 71–88, 2005, proceedings of the International
Conference on Analytic Number Theory with Special Emphasis on L-functions held in Chen-
nai, January 2002.
[15] C. E. Praeger, C. H. Li and A. C. Niemeyer, Finite transitive permutation groups and finite
vertex-transitive graphs, in: G. Hahn and G. Sabidussi (eds.), Graph Symmetry: Algebraic
Methods and Applications, Kluwer Academic Publishers Group, Dordrecht, volume 497 of
NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences, pp. 277–
318, 1997, doi:10.1007/978-94-015-8937-6 7, proceedings of the NATO Advanced Study In-
stitute and the Séminaire de Mathématiques Supérieures held in Montreal, PQ, July 1 – 12,
1996.
[16] G. Ricci, Ricerche aritmetiche sui polinomi, Rend. Circ. Mat. Palermo 57 (1933), 433–475.
[17] D. J. S. Robinson, A Course in the Theory of Groups, volume 80 of Graduate Texts in Mathe-
matics, Springer-Verlag, New York, 2nd edition, 1996, doi:10.1007/978-1-4419-8594-1.
[18] M. A. Snyder, Chebyshev Methods in Numerical Approximation, Prentice-Hall, Englewood
Cliffs, NJ, 1966.