Pith. sign in

REVIEW 2 major objections 4 minor 18 references

Some Algebraic Properties of Sierpi\'nski-Type Graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that the regular generalized Sierpiński graph $S^{++}(n,k)$ is a Cayley graph exactly when $n=1$, $k\le 2$, or $n=2$ with $k+1$ a prime power.

desk verdict A solid, self-contained contribution to Sierpiński-type graphs: clean spectrum recursion, a full Cayley classification, and new non-Cayley numbers; one unproved but fillable cut-vertex claim is the main soft spot. read the letter →

arxiv 1908.04037 v4 pith:WJQPWZ6G submitted 2019-08-12 math.CO math.DS

Mohammad Farrokhi Derakhshandeh Ghouchan , E. Ghorbani , H. R. Maimani , F. Rahimi Mahid This is my paper · ORCID
classification math.COmath.DS MSC 05C5005C2505C75
keywords SierpińskigraphregulargeneralizedspectrumLaplacianCayleynon-Cayleynumbervertex-transitiveFrobeniusgroup
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies two families of Sierpiński-type graphs: the classical Sierpiński graphs $S(n,k)$, whose vertices are the $k^n$ strings of length $n$ over $k$ symbols, and their regularized relatives $S^{++}(n,k)$, built by gluing $k+1$ copies of $S(n-1,k)$ along a complete graph on the extreme vertices. Its central result is a complete classification of when these regularized graphs are Cayley graphs—graphs whose vertices are group elements and whose edges come from multiplying by a fixed connection set: $S^{++}(n,k)$ is a Cayley graph exactly when $n=1$, $k\le 2$, or $n=2$ and $k+1$ is a prime power. For $n=2$ with $k+1$ not a prime power, the graphs are vertex-transitive (their automorphism group acts transitively on vertices) but not Cayley, which yields new non-Cayley numbers. The paper also computes the full adjacency spectrum of $S^{++}(n,k)$ as nested radicals built from iterating one quadratic polynomial, determines the Laplacian spectrum of $S(2,k)$, and conjectures the Laplacian spectrum of all $S(n,k)$.

What carries the argument

The central object is the recursion $S^{++}(n+1,k)\cong L(S(S^{++}(n,k)))$, where $S(\Gamma)$ is the graph obtained by inserting a new vertex into every edge of $\Gamma$ and $L(\Gamma)$ is the line graph whose vertices are the edges of $\Gamma$. This identity converts the characteristic polynomial into a composition: $P_n(x)=(x(x+2))^{k^{n-2}(\binom{k}{2}-1)}P_{n-1}(f(x))$, with $f(x)=x^2+(2-k)x-k$, so every eigenvalue of $S^{++}(n,k)$ is a nested-radical expression built from iterates $f^j$. For the Cayley classification, the load-bearing tool is the notion of a strongly $\Delta$-partitioned graph: a graph whose vertices are partitioned by copies of $\Delta$ and which contains no further copies of $\Delta$. Applied to a Cayley graph, this forces the copies to be cosets of a subgroup; in the case $n=2$ the copies are complete graphs, and a Frobenius-group argument forces the order of each copy plus one, $k+1$, to be a prime power.

What would settle it

A computer search over all groups of order 30 for a connection set whose Cayley graph is isomorphic to $S^{++}(2,5)$ would settle the classification in this case; the theorem predicts no such Cayley presentation exists.

Watch

Extended reading notes

Core claim

The paper's main discovery is Theorem 14: $S^{++}(n,k)$ is a Cayley graph if and only if $n=1$, $k\le 2$, or $n=2$ and $k+1$ is a prime power. The 'if' direction is constructive: when $k+1=q$ is a prime power, $S^{++}(2,q-1)$ is shown to be the Cayley graph of the one-dimensional affine group $\mathbb{F}_q^*\ltimes\mathbb{F}_q$ with connection set $\{(x,0): x\neq 1\}\cup\{(-1,-1)\}$. The 'only if' direction combines two structural facts: for $n\ge 3, k\ge 3$ the graph is not even vertex-transitive, and for $n=2$ a strongly-partitioned Cayley graph argument forces $k+1$ to be a prime power. Along the way the paper proves that $S^{++}(n+1,k)$ is the line graph of the subdivision graph of $S^{++}(n,k)$, which yields the spectrum recursion $P_n(x)=(x(x+2))^{k^{n-2}(\binom{k}{2}-1)}P_{n-1}(f(x))$ with $f(x)=x^2+(2-k)x-k$. The paper also determines the Laplacian spectrum of $S(2,k)$ and conjectures an explicit formula for $S(n,k)$.

Load-bearing premise

The only-if direction of the classification for $n\ge 3$, $k\ge 3$ rests on the assertion, stated without full proof, that in the subgraph of vertices within three steps the vertex $(1,\dots,1,1)$ is a cut vertex while $(1,\dots,1,2)$ is not; if that distinction fails, these graphs might still be vertex-transitive and the non-Cayley conclusion for them loses its support.

Editorial extensions

If this is right

  • For every $k\ge 3$ with $k+1$ not a prime power, $S^{++}(2,k)$ is a vertex-transitive graph that is not a Cayley graph; together with the $n\ge 3$, $k\ge 3$ cases, this gives a new infinite family of vertex-transitive non-Cayley graphs.
  • Every integer $k(k+1)$ with $k(k+1)$ square-free and $k+1$ composite is a non-Cayley number, so the known list of non-Cayley numbers grows; the paper identifies eight new examples below $10^8$.
  • The spectrum of $S^{++}(n,k)$ is fully determined by iterates of the single polynomial $f(x)=x^2+(2-k)x-k$, so all eigenvalues are obtained as nested radicals without diagonalizing large matrices.
  • The Laplacian spectrum of $S(2,k)$ is explicitly known, and the conjecture that the same formula holds for all $S(n,k)$ gives a concrete prediction to test.
  • The density calculation says the set of $k$ for which $k(k+1)$ is a new non-Cayley number has asymptotic density about $0.3226$, so these numbers are not rare.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same Frobenius-group obstruction may explain non-Cayley-ness in other recursively defined graph families built from complete graphs; comparing the paper's example of $SP_1(C_4)$ for order $20$ with the case where the number of copies plus one is composite could reveal whether the prime-power condition is a general structural principle.
  • The iterated-polynomial form of the spectrum suggests that as $n$ grows, the spectral distribution of $S^{++}(n,k)$ may converge to the equilibrium measure of the Julia set of $f(x)=x^2+(2-k)x-k$; a numerical study of the empirical eigenvalue distribution for moderate $n$ could test this.
  • If the Laplacian conjecture is correct, the heat-kernel and random-walk return probabilities on Sierpiński gasket graphs have a closed form in terms of iterates of $f$, which would give a concrete tool for diffusion models on these fractal networks.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies the Sierpiński graphs S(n,k) and the regularized family S++(n,k). In Section 2 the authors derive a recursive formula for the characteristic polynomial of S++(n,k) via the relation S++(n+1,k) ≅ L(S(S++(n,k))), and from it obtain the full spectrum of S++(n,k). Section 3 determines the Laplacian spectrum of S(2,k), verifies the resulting conjecture for k=2,3 and n=2, and states a general conjecture for the Laplacian spectrum of S(n,k). Section 4 characterizes the vertex-transitive graphs in the family (Proposition 9) and then classifies which S++(n,k) are Cayley graphs: they are Cayley exactly when n=1, k≤2, or n=2 and k+1 is a prime power (Theorem 14). As a by-product, the authors obtain new vertex-transitive non-Cayley graphs and a positive-density family of non-Cayley numbers.

Significance. If the main results are correct, Theorem 14 is a complete classification of the Cayley graphs in a substantial infinite family, and it supplies a new infinite family of vertex-transitive non-Cayley graphs and new square-free non-Cayley numbers. The proof strategy is attractive: the spectral recursion via incidence matrices and line graphs is elegant, and the Cayley characterization via Frobenius groups is a genuine structural use of group theory. The paper is largely self-contained and the arguments rely only on standard external results (McKay-Praeger, Ricci, Frobenius). The explicit Cayley construction for the prime-power case and the density computation for non-Cayley numbers are concrete and checkable. The main issues are two proof gaps, one in the load-bearing Proposition 9 and one in the proof of Theorem 4, both of which appear fixable without changing the stated results.

major comments (2)
  1. [Section 4, Proposition 9] The assertion that for n≥3, k≥3 the vertex u=(1,...,1,1) is a cut vertex of the induced subgraph on B(u,3) while v=(1,...,1,2) is not is stated only as "It can be seen" and is not proved. This claim is load-bearing: it is the only reason given for non-vertex-transitivity of S++(n,k) for n≥3, k≥3, and therefore for the only-if direction of Theorem 14 for those parameters. The assertion appears true, and a proof can likely be supplied by distance arguments (every path from a neighbor of u outside its copy to B(u,3) that avoids u must pass through vertices at distance at least 4 from u, while v admits an explicit alternate path inside B(v,3)), but as written the paper does not establish it. The authors should provide a complete proof or a precise reference.
  2. [Section 3, Theorem 4] In the proof of Theorem 4, after showing that (L^2-(k+2)L+kI)(QB-BQ)=0, the text states that every vector in the column space of QB-BQ is an eigenvector of L with eigenvalue satisfying λ^2-(k+2)λ+k=0. This does not follow: a nonzero vector w with p(L)w=0 for a quadratic polynomial p need not be an eigenvector. The intended conclusion can be obtained because the column space W is L-invariant and p is irreducible over Q, so the minimal polynomial of L restricted to W is p and W decomposes into the two eigenspaces, each of dimension k-1; this argument should be stated explicitly. As written, the multiplicity conclusion for the two roots is not fully justified.
minor comments (4)
  1. [Section 1] In the last paragraph of the introduction, "non-Calyley" should be "non-Cayley".
  2. [Section 4, Proposition 9] In the proof of Proposition 9, "vertices at distance at most 3 form u" should read "from u", and similarly for v.
  3. [Section 5] In the final paragraph, "leass than or equal to" should be "less than or equal to".
  4. [Theorem 19] The title of Theorem 19 says the density is "about 0.3226", while the proof actually obtains the exact value 2C_FT-1 ≈ 0.3226340989; it would be clearer to state the exact density in the theorem and reserve the approximation for the text.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: spectral and Cayley classifications are derived in-paper from explicit isomorphisms, determinant identities, and external standard theorems; the one unproved cut-vertex assertion is a proof gap, not a circular reduction.

full rationale

The paper's main claims are self-contained derivations against external benchmarks. The spectrum of S++(n,k) (Theorem 2) follows from the explicitly proved isomorphism S++(n+1,k) ≅ L(S(S++(n,k))) (Lemma 1) together with standard incidence-matrix identities (1), (2), (3), (4); no parameter is fitted to the target spectrum. The Laplacian spectrum of S(2,k) (Theorem 4) is computed directly via the commutation matrix and eigenspace dimension counting; the general formula is explicitly labeled Conjecture 5, not asserted as a derived prediction. The Cayley classification (Theorem 14) is built from Proposition 9, Proposition 10, Lemma 11, and Theorem 13, each proved in the paper using standard group theory (Frobenius groups, Robinson [17]) and elementary graph arguments. The sufficiency direction is an explicit construction of Cay(G,C) for the one-dimensional affine group, and necessity reduces to Theorem 13, whose proof is internal and does not import the conclusion. Proposition 9's assertion that u=(1,...,1,1) is a cut vertex of its 3-ball while v=(1,...,1,2) is not, stated as 'It can be seen,' is indeed load-bearing but is an unproved local graph claim, not a reduction of the conclusion to the hypothesis; a gap in proof detail is a correctness concern, not circularity. External results are used only for background: McKay-Praeger for non-Cayley number classifications, Dobson-Spiga for Cayley numbers, and Ricci's density theorem for the square-free density; none supplies the paper's target conclusions by renaming. No self-citation chain appears, and no fitted input is called a prediction. Honest finding: no significant circularity.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

No free parameters are fitted; the spectra and classifications are derived. The paper relies on standard matrix identities, Frobenius group theory, Ricci's density theorem, and prior classifications of Cayley numbers. These are external results, not restatements of the present claims.

assumptions (8)
  • standard math Incidence matrix identities X(Γ)^T X(Γ)=2I+A(L(Γ)) and X(Γ)X(Γ)^T=kI+A(Γ) for k-regular Γ.
    Used in the proof of Theorem 2, Section 2, to derive the characteristic polynomial recursion.
  • standard math Determinant identities for block matrices and for products M M^T versus M^T M.
    Used in Theorem 2 proof via equations (3) and (4).
  • standard math Frobenius theorem: a Frobenius group with complement H has a normal kernel N = G \ union of conjugates of H\{1}.
    Invoked in Theorem 13 proof via Robinson [17] to force the group structure.
  • standard math The Frobenius kernel is nilpotent and its characteristic subgroups inherit normality.
    Used in Theorem 13 to conclude the kernel is elementary abelian of prime power order, citing Robinson [17, 10.5.1(i)] and [17, 1.5.6].
  • standard math Ricci's theorem on the asymptotic density of k-free values of polynomials.
    Used in Theorem 19 for the density of square-free k(k+1).
  • domain assumption Known classifications of Cayley numbers: McKay-Praeger for non-square-free numbers and Iranmanesh-Praeger plus Dobson-Spiga for products of primes.
    Background for Section 5; these results are not derived in this paper.
  • domain assumption The Grigorchuk-Šunić spectrum of the Hanoi Towers Schreier graph implies the Laplacian spectrum of S(n,3).
    Used in Remark 7 to state that Conjecture 5 holds for k=3.
  • domain assumption Every edge of S(n-1,k) for k≥3 lies on a cycle.
    Used in Proposition 10 proof for n≥3; asserted with a parenthetical 'which can be seen by induction on n' and not fully proved.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Some Algebraic Properties of Sierpi\'nski-Type Graphs." pith.science (2026). https://pith.science/paper/WJQPWZ6G

@misc{pith2026190804037,
  author       = {Pith},
  title        = {Pith review of: Some Algebraic Properties of Sierpi\'nski-Type Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WJQPWZ6G}},
  note         = {Machine review of arXiv:1908.04037}
}
read the original abstract

This paper deals with some of the algebraic properties of Sierpi\'nski graphs and a family of regular generalized Sierpi\'nski graphs. For the family of regular generalized Sierpi\'nski 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\'nski graphs in some particular cases, and make a conjecture on the general case.

Figures

Figures reproduced from arXiv: 1908.04037 by the authors.

Figure 1
Figure 1. The Sierpi´nski graphs S(3, 3) (left) and S(2, 4) (right) S(n, k) were introduced in Klavˇzar and Milutinovi´c [8]. The graph S(n, 3) is indeed isomor￾phic to the graph of the Tower of Hanoi with n disks. The graph S(n, k) has k n −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 ‘regulariz… view at source ↗
Figure 2
Figure 2. The graph S ++(3, 3) 2 [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Barri` ere, F

    L. Barri` ere, F. Comellas, and C. Dalf´ o, Fractality and the small-world effect in Sier- pinski graphs, J. Phys. A 39 (2006), 11739–11753

    work page 2006

  2. [2]

    D. M. Cvetkovi´ c, M. Doob, and H. Sachs, Spectra of Graphs, Theory and Applications , Third Edition, Johann Ambrosius Barth, Heidelberg, 1995

    work page 1995

  3. [3]

    Dobson and P

    T. Dobson and P. Spiga, Cayley numbers with arbitrarily m any distinct prime factors, J. Combin. Theory Ser. B 122 (2017), 301–310

    work page 2017

  4. [4]

    S. R. Finch, Mathematical Constants , Encyclopedia of Mathematics and its Applica- tions, 94, Cambridge University Press, Cambridge, 2003

    work page 2003

  5. [5]

    R. I. Grigorchuk and Z. ˇSuni´ c, Schreier spectrum of the Hanoi towers group on three pegs, Proc. Symp. Pure Math. 77 (2008), 183–198

    work page 2008

  6. [6]

    A. M. Hinz, S. Klavˇ zar, and S. S. Zemljiˇ c, A survey and classification of Sierpi´ nski-type graphs, Discrete Appl. Math. 217 (2017), 565–600

    work page 2017

  7. [7]

    M. A. Iranmanesh and C. E. Praeger, On non-Cayley vertex- transitive graphs of order a product of three prime, J. Combin. Theory Ser. B 81 (2001), 1–19

    work page 2001

  8. [8]

    Klavˇ zar and U

    S. Klavˇ zar and U. Milutinovi´ c, Graphs S(n,k ) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47(122) (1997), 95–104

    work page 1997

Show all 18 references
  1. [9]

    Klavˇ zar and B

    S. Klavˇ zar and B. Mohar, Crossing numbers of Sierpi´ nski-like graphs, J. Graph Theory 50 (2005), 186–198

    2005

  2. [10]

    J. R. Magnus and H. Neudecker, The commutation matrix: s ome properties and ap- plications, Ann. Statist. 7 (1979), 381–394

    1979

  3. [11]

    Maruˇ siˇ c, Cayley properties of vertex symmetric graphs, Ars Combin

    D. Maruˇ siˇ c, Cayley properties of vertex symmetric graphs, Ars Combin. 16B (1983), 297–302

    1983

  4. [12]

    B. D. McKay and C. E. Praeger, Vertex-transitive graphs which are not Cayley graphs, I, J. Austral. Math. Soc. (A) 56 (1994), 53–63

    1994

  5. [13]

    B. D. McKay and C. E. Praeger, Vertex-transitive graphs that are not Cayley graphs, II, J. Graph Theory 22(4) (1996), 321–334

    1996

  6. [14]

    Pappalardi, A survey on k-freeness, Number Theory, Ramanujan Math

    F. Pappalardi, A survey on k-freeness, Number Theory, Ramanujan Math. Soc. Lect. Notes Ser., vol. 1, Ramanujan Math. Soc. (2005), pp. 71–88. 15

    2005

  7. [15]

    C. E. Praeger, C. H. Li, and A. C. Niemeyer, Finite transi tive permutation groups and finite vertex-transitive graphs, Graph Symmetry: Algebraic Methods and Applications, NATO Ser. C, 497, Kluwer Acad. Publ. (1997), pp. 277–318

    1997

  8. [16]

    Ricci, Ricerche aritmetiche sui polinomi, Rend

    G. Ricci, Ricerche aritmetiche sui polinomi, Rend. Circ. Mat. Palermo 57 (1933), 433– 475

    1933

  9. [17]

    D. J. S. Robinson, A Course in the Theory of Groups , Second Edition, Spring-Verlag, New York, 1996

    1996

  10. [18]

    M. A. Snyder, Chebyshev Methods in Numerical Approximation , Prentice-Hall, Inc., Englewood Cliffs, N. J. 1966. 16

    1966

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.