pith. sign in

arxiv: 2605.22867 · v1 · pith:XZEURTQPnew · submitted 2026-05-19 · 🧮 math.CO

A Comprehensive Study of Clique Graphs and Clique Regular Graphs

Connor Phillips This is my paper

Pith reviewed 2026-05-25 05:45 UTC · model grok-4.3

classification 🧮 math.CO
keywords clique graphsclique regular graphsstrongly regular graphsspectral boundscritical groupsgraph transformationsexistence results
0
0 comments X

The pith

Graphs where every edge lies in exactly one clique of order ω admit a clique graph that bounds the spectrum of the original graph.

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

The paper studies graphs Γ in which every edge belongs to precisely one clique of size ω. From these graphs a clique graph is formed whose vertices are the ω-cliques; this construction generalizes the line graph. Spectral bounds on Γ are obtained from the clique graph, with exact eigenvalues when Γ is regular. Complete classifications follow when Γ is strongly regular, and these classifications supply new existence information for certain strongly regular graphs. The critical groups of such graphs and their transformations are also examined, together with concrete families that satisfy the edge-clique condition.

Core claim

If Γ is a graph for which every edge is in exactly one clique of order ω, then the associated clique graph yields bounds on the spectrum of Γ (exact when Γ is k-regular) and complete classifications when Γ is strongly regular; these results produce new information on the existence of certain strongly regular graphs and allow study of the critical group under the associated transformations.

What carries the argument

The clique graph whose vertices are the ω-cliques that partition the edges of Γ.

If this is right

  • When Γ is k-regular the eigenvalues of Γ are determined exactly by parameters of the clique graph.
  • Strongly regular graphs with the unique-clique property fall into finitely many classified families in given parameter ranges.
  • Existence questions for specific strongly regular graphs are settled by checking whether they admit the clique-graph construction.
  • The critical group of Γ is related to the critical group of its clique graph by an explicit transformation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same construction may relate other algebraic invariants such as the Laplacian spectrum or the sandpile group across the clique graph and original graph.
  • Families of graphs already known to satisfy the edge-clique condition (certain designs or geometries) can be used to test the spectral formulas directly.
  • The property may serve as a recognition criterion for graphs whose spectra are constrained in ways useful for coding or combinatorial search problems.

Load-bearing premise

Every edge of Γ belongs to exactly one clique of order ω.

What would settle it

A concrete k-regular graph satisfying the unique-clique property whose spectrum falls outside the claimed bounds.

Figures

Figures reproduced from arXiv: 2605.22867 by Connor Phillips.

Figure 1.1
Figure 1.1. Figure 1.1: An example of a clique regular graph and its clique graph [PITH_FULL_IMAGE:figures/full_fig_p009_1_1.png] view at source ↗
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 2
Figure 2. Figure 2: b consists of four triangles with each pair sharing at least one vertex, so [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 2
Figure 2. Figure 2: b consists of four triangles all sharing vertex 4, so [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 4.1
Figure 4.1. Figure 4.1: The neighborhood of v and the Ti sets The authors of [14] used a counting argument to derive a general system of linear equations that walk-regular graphs must satisfy, and for graph C3(Γ) this system is: τ0 + τ1 + τ2 + τ3 = m − d − 1, τ1 + 2τ2 + 3τ3 = d(d − 1) − 2∆, τ2 + 3τ3 = Ξ −  d/3 − 1 2  d. (4.5) For a graph with the properties of C3(Γ) to exist, there must be at least one positive integer soluti… view at source ↗
Figure 5.1
Figure 5.1. Figure 5.1: An example of the clique subdivision graph [PITH_FULL_IMAGE:figures/full_fig_p049_5_1.png] view at source ↗
Figure 6
Figure 6. Figure 6 [PITH_FULL_IMAGE:figures/full_fig_p060_6.png] view at source ↗
Figure 6
Figure 6. Figure 6 [PITH_FULL_IMAGE:figures/full_fig_p063_6.png] view at source ↗
read the original abstract

If $\Gamma$ is a graph for which every edge is in exactly one clique of order $\omega$, then one can form a new graph with vertex set equal to these cliques. This is a generalization of the line graph of $\Gamma$. We discover many general results and classifications related to these clique graphs that will be useful to researchers studying graphs with this property. In particular, we find bounds on the spectrum of $\Gamma$ (with exact results when $\Gamma$ is $k$-regular) and some complete classifications when $\Gamma$ is strongly regular. We apply our results to derive novel information about the existence questions of certain strongly regular graphs. We also examine the critical group of graphs with this property and their associated transformations. Finally, we discuss examples of widely studied families of graphs that have this property, and provide some examples to make the results more concrete.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper studies graphs Γ where every edge lies in exactly one clique of order ω. It defines the associated clique graph (a generalization of the line graph), derives bounds on the spectrum of Γ (exact when Γ is k-regular), gives complete classifications in the strongly regular case, applies the results to obtain new existence information for certain strongly regular graphs, examines the critical group under the associated transformations, and discusses examples from known families.

Significance. If the spectral bounds, classifications, and existence applications are correct, the work would supply a coherent framework extending line-graph techniques to a broader class of clique-regular graphs and could contribute concrete information to open questions on strongly regular graphs. The inclusion of critical-group results adds an algebraic-combinatorial dimension.

major comments (1)
  1. [Abstract] Abstract and introduction: the central claims (spectral bounds with exact results for k-regular graphs, complete classifications for strongly regular Γ, and novel existence information for SRGs) are stated without any theorem statements, equations, or proof sketches. Because these results are the load-bearing contributions, their absence prevents verification that the derivations are independent of the defining property and free of hidden parameters.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for recognizing the potential value of the framework extending line-graph techniques. We address the single major comment below and will revise the manuscript accordingly to improve accessibility of the central results.

read point-by-point responses

  1. Referee: [Abstract] Abstract and introduction: the central claims (spectral bounds with exact results for k-regular graphs, complete classifications for strongly regular Γ, and novel existence information for SRGs) are stated without any theorem statements, equations, or proof sketches. Because these results are the load-bearing contributions, their absence prevents verification that the derivations are independent of the defining property and free of hidden parameters.

    Authors: We agree that the abstract and introduction, as currently written, present the main results at a high level without explicit theorem statements, equations, or sketches. This choice was made to maintain brevity, but we recognize that it hinders immediate verification of independence from the defining property. In the revised manuscript we will expand both the abstract and the introduction to include: (i) the precise statement of the spectral bound (including the exact eigenvalue formula for k-regular graphs), (ii) the classification theorems for strongly regular graphs, and (iii) a brief indication of how the existence applications follow from the preceding results. These additions will be placed after the definition of the clique graph and will reference the relevant sections of the paper, thereby making the logical independence from the unique-clique-cover hypothesis explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results follow directly from the defining property

full rationale

The paper defines a graph class via the property that every edge lies in exactly one K_ω, constructs the associated clique graph (a direct generalization of the line graph), and derives spectral bounds, classifications for strongly regular members, and applications to SRG existence questions from this structural assumption. No equations, self-citations, fitted parameters, or uniqueness theorems are quoted that reduce any claimed result to its own inputs by construction. The derivation chain is self-contained against the given definition, with no load-bearing steps that collapse into renaming, ansatz smuggling, or self-referential fitting.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No information is available from the abstract on free parameters, background axioms, or newly postulated entities.

pith-pipeline@v0.9.0 · 5664 in / 1244 out tokens · 25750 ms · 2026-05-25T05:45:26.720064+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · 1 internal anchor

  1. [1]

    Abadir and J.R

    K.M. Abadir and J.R. Magnus.Matrix Algebra. Econometric Exercises. Cambridge University Press, 2005. URL:https://books.google.com/books?id=1I70zwUf1cAC

    work page 2005

  2. [2]

    Apostol.Introduction to analytic number theory

    Tom M. Apostol.Introduction to analytic number theory. Springer, 1976

    work page 1976

  3. [3]

    The critical group of a line graph

    Andrew Berget, Andrew Manion, Molly Maxwell, Aaron Potechin, and Victor Reiner. The critical group of a line graph, 2010. URL:https://arxiv.org/abs/0904.1246, arXiv:0904.1246

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  4. [4]

    Cambridge Mathematical Library

    Norman Biggs.Algebraic graph theory. Cambridge Mathematical Library. Cambridge University Press, Cambridge, second edition, 1993

    work page 1993

  5. [5]

    Andries E. Brouwer. Parameters of strongly regular graphs. URL: https://aeb.win.tue.nl/graphs/srg/srgtab.html

    work page

  6. [6]

    Brouwer and Willem H

    Andries E. Brouwer and Willem H. Haemers.Spectra of graphs. Universitext. Springer, New York, 2012.doi:10.1007/978-1-4614-1939-6

    work page doi:10.1007/978-1-4614-1939-6 2012

  7. [7]

    Z3: An efficient smt solver

    Leonardo de Moura and Nikolaj Bjørner. Z3: An efficient smt solver. In C. R. Ramakrishnan and Jakob Rehof, editors,Tools and Algorithms for the Construction and Analysis of Systems, pages 337–340, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg

    work page 2008

  8. [8]

    C. D. Godsil and Gordon Royle.Algebraic graph theory. Graduate texts in mathematics ; 207. Springer, New York, 2001. 66

    work page 2001

  9. [9]

    Cambridge University Press, Cambridge, 2016.doi:10.1017/CBO9781316414958

    Chris Godsil and Karen Meagher.Erd˝ os-Ko-Rado theorems: algebraic approaches, volume 149 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2016.doi:10.1017/CBO9781316414958

    work page doi:10.1017/cbo9781316414958 2016

  10. [10]

    Guest, James M

    Kelly B. Guest, James M. Hammer, Peter D. Johnson, and Kenneth J. Roblee. Regular clique assemblies, configurations, and friendship in edge-regular graphs. Tamkang Journal of Mathematics, 48:301–320, 2017. doi:10.5556/j.tkjm.48.2017.2237

    work page doi:10.5556/j.tkjm.48.2017.2237 2017

  11. [11]

    Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969

    Frank Harary.Graph theory. Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969

    work page 1969

  12. [12]

    Magnus and H

    J.R. Magnus and H. Neudecker.Matrix Differential Calculus with Applications in Statistics and Econometrics. PROBABILISTICS AND STATISTICS. Wiley, 1988. URL:https://books.google.com/books?id=0CXXdKKiIpQC

    work page 1988

  13. [13]

    Sympy 1.14.0 documentation, Apr 2025

    SymPy. Sympy 1.14.0 documentation, Apr 2025. URL:https://docs.sympy.org/ latest/modules/ntheory.html#sympy.ntheory.factor_.factorint

    work page 2025

  14. [14]

    van Dam and Edward Spence

    Edwin R. van Dam and Edward Spence. Small regular graphs with four eigenvalues. Discrete Mathematics, 189(1):233–257, 1998. URL: https://www.sciencedirect.com/science/article/pii/S0012365X98000855, doi:10.1016/S0012-365X(98)00085-5

    work page doi:10.1016/s0012-365x(98)00085-5 1998

  15. [15]

    Congruent Graphs and the Connectivity of Graphs.Amer

    Hassler Whitney. Congruent Graphs and the Connectivity of Graphs.Amer. J. Math., 54(1):150–168, 1932.doi:10.2307/2371086. 67

    work page doi:10.2307/2371086 1932