{"id":"3b06ee54-0f7a-4004-aaa5-ab8e1a3006df","arxiv_id":"1908.04037","paper_version":4,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For the regular Sierpiński graphs S++(n,k), the spectrum is computed and S++(n,k) is shown to be a Cayley graph exactly when n=1, k≤2, or n=2 and k+1 is a prime power.","lead":"This paper determines the eigenvalues of a family of regular Sierpiński-type graphs and proves exactly when they are Cayley graphs. It uses that result to produce a new infinite family of vertex-transitive graphs that are not Cayley, and a new list of non-Cayley numbers.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 9's unproved cut-vertex assertion is the load-bearing weak spot, but it appears true and checkable; no correctness flaw found.","rationale":"The paper's central claim is the Cayley classification of S++(n,k). Theorem 13's Frobenius argument and the affine-group construction for prime powers are internally consistent; the SP_1(K_k) structure of S++(2,k) is correctly identified, with exactly one inter-copy edge per pair of copies as Lemma 1 shows. The only genuinely unproved load-bearing statement is the local cut-vertex dichotomy in Proposition 9. The reader's weakest_assumption points to the same passage, and my manual checks plus the explicit path above indicate the statement is true, so the classification is not endangered. The gap is expositary and easily fillable, and therefore does not change the ACCEPT verdict.","tokens_in":14153,"tokens_out":52428,"duration_ms":499130,"concrete_test":"Write a BFS program for S++(n,k) using Lemma 1's adjacency and verify for n=3,...,6 and k=3,...,6 that u is a cut vertex of B(u,3), while v is not a cut vertex of B(v,3). Alternatively, check algebraically that the seven vertices z-b-m-q-w-u listed above are all in B(v,3), are distinct from v, and that consecutive pairs are edges; this settles the non-cut half for all n≥3,k≥3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4, Proposition 9: the claim 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 asserted only as 'It can be seen...' with no proof. This is load-bearing: it is the sole reason S++(n,k) is not vertex-transitive for n≥3,k≥3, hence the only-if half of Theorem 14 for those parameters. The assertion appears true: in S(n-1,k) the distance between the extreme vertices labeled 1 and i≥2 is at least 3, so every exit from copy 1 except through u pushes outside vertices to distance ≥4, making u a cut vertex of its 3-ball; for v an explicit alternative path z-b-m-q-w-u (with z=(1,...,1,2,1), b=(1,...,1,2,3), m=(1,...,1,3,2), q=(1,...,1,3,1), w=(1,...,1,3)) stays inside B(v,3) and avoids v, showing v is not a cut vertex. Thus the gap is real but fillable; no counterexample is evident.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14352,"tokens_out":36821,"duration_ms":333176,"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":[{"comment":"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.","section":"Section 4, Proposition 9"},{"comment":"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.","section":"Section 3, Theorem 4"}],"minor_comments":[{"comment":"In the last paragraph of the introduction, \"non-Calyley\" should be \"non-Cayley\".","section":"Section 1"},{"comment":"In the proof of Proposition 9, \"vertices at distance at most 3 form u\" should read \"from u\", and similarly for v.","section":"Section 4, Proposition 9"},{"comment":"In the final paragraph, \"leass than or equal to\" should be \"less than or equal to\".","section":"Section 5"},{"comment":"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.","section":"Theorem 19"}],"recommendation":"major_revision","confidential_remarks":"The paper appears to be within the scope of the journal and the main results are likely correct. The two proof gaps identified above, especially the unproved cut-vertex assertion in Proposition 9, should be addressed before publication. I do not see grounds for rejection, but the load-bearing nature of Proposition 9 for Theorem 14 makes the current version unsuitable for acceptance as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a solid paper. The spectrum of S++(n,k) is derived through a neat recursion using incidence matrices and the line graph relation, and the Cayley classification in Theorem 14 is a genuine contribution: it completely settles which S++(n,k) are Cayley graphs, and the connection to Frobenius groups is elegant. The new non-Cayley numbers coming out of the k(k+1) construction are a real extra, and the density calculation using Ricci's theorem is correct.\n\nWhat is new: the spectrum recursion for S++ (Theorem 2), the Laplacian spectrum for S(2,k) (Theorem 4), the Cayley/non-Cayley classification (Theorem 14), and the specific non-Cayley numbers in Section 5. The proofs are structured and self-contained, relying on standard outside results (McKay–Praeger, Ricci, Frobenius). No circularity or invented entities.\n\nThe main soft spot is Proposition 9. The claim that u=(1,...,1,1) is a cut vertex of its 3-ball while v=(1,...,1,2) is not is stated with \"It can be seen\" and no proof. This is load-bearing: it is the sole reason S++(n,k) is not vertex-transitive for n≥3,k≥3, and hence drives the only-if direction of Theorem 14. The assertion looks true—for u, every edge leaving copy 1 except through u pushes to distance ≥4; for v, there is an explicit 6-cycle inside the 3-ball avoiding v. So the gap is fillable, but it needs a proof. Minor issue: in Theorem 4, the argument that an irreducible quadratic's roots each appear with multiplicity at least k−1 is terse; a trace or rational eigenspace argument completes it. Also, Conjecture 5 is explicitly a conjecture, so no issue.\n\nWho it's for: algebraic graph theorists working on Sierpiński-type graphs, Cayley graph recognition, or non-Cayley numbers. The paper earns a serious referee and should be accepted after a minor revision that fills in the proof of Proposition 9 and clarifies Theorem 4. I'd take it to a reading group only if the group does algebraic graph theory, but I'd cite the classification in my own work.","headline":"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.","tokens_in":14939,"tokens_out":3124,"would_cite":true,"duration_ms":27577,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C25","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Sierpiński graph","regular generalized Sierpiński graph","spectrum","Laplacian spectrum","Cayley graph","non-Cayley number","vertex-transitive graph","Frobenius group"],"falsifier":"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.","tokens_in":13955,"feed_emoji":"🔺","tokens_out":18218,"duration_ms":138170,"temperature":0.7,"pith_summary":"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)$.","feed_headline":"Regularized Sierpiński graphs: Cayley iff n=1, k≤2, or k+1 prime power","feed_subtitle":"That yields new vertex-transitive graphs that are not Cayley, plus new non-Cayley numbers.","key_machinery":"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.","core_discovery":"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)$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the Sierpiński graphs $S(n,k)$ from which the regularized family is built.","marker":"[8]"},{"why":"Introduces the graphs $S^{++}(n,k)$; its definition and recursive structure feed Lemma 1.","marker":"[9]"},{"why":"Provides the commutation-matrix identity used in the proof of the Laplacian spectrum of $S(2,k)$.","marker":"[10]"},{"why":"States the theorem on non-square-free Cayley numbers that frames the non-Cayley-number results.","marker":"[13]"},{"why":"Gives the density theorem for square-free polynomial values used to estimate the frequency of new non-Cayley numbers.","marker":"[16]"}],"fun_headline_variants":["Sierpiński graphs: Cayley iff n=1, k≤2, or k+1 prime power","New non-Cayley vertex-transitive graphs from Sierpiński","Cayley Sierpiński graphs: n=1, k≤2, or k+1 prime power","Generalized Sierpiński graphs: Cayley iff n=1, k≤2, or k+1 prime power"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sierpiński graphs: Cayley iff n=1, k≤2, or k+1 prime power","New non-Cayley vertex-transitive graphs from Sierpiński","Cayley Sierpiński graphs: n=1, k≤2, or k+1 prime power","Generalized Sierpiński graphs: Cayley iff n=1, k≤2, or k+1 prime power"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00267,"raw_usage":{"total_tokens":10204,"prompt_tokens":958,"completion_tokens":9246,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":9138}},"tokens_in":574,"tokens_out":9246,"duration_ms":65760,"temperature":1.0,"reasoning_tokens":9138,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:56:27.839498+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Klavˇ zar and U","cited_arxiv_id":null,"evidence_quote":"Introduces the Sierpiński graphs $S(n,k)$ from which the regularized family is built."},{"cited_title":"Klavˇ zar and B","cited_arxiv_id":null,"evidence_quote":"Introduces the graphs $S^{++}(n,k)$; its definition and recursive structure feed Lemma 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the commutation-matrix identity used in the proof of the Laplacian spectrum of $S(2,k)$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the theorem on non-square-free Cayley numbers that frames the non-Cayley-number results."},{"cited_title":"Ricci, Ricerche aritmetiche sui polinomi, Rend","cited_arxiv_id":null,"evidence_quote":"Gives the density theorem for square-free polynomial values used to estimate the frequency of new non-Cayley numbers."}],"review_version":1}