Extremal Graphs for the Energy-Independence Number Inequality

Seyed Ahmad Mojallal

REVIEW 2 major objections 3 minor 12 references

Extremal Graphs for the Energy-Independence Number Inequality

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

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

Pith's one-line read Every graph that attains the energy–independence lower bound decomposes into isolated vertices, balanced complete multipartite graphs, or $H_r(a,b)$ with $r\ge 3$.

desk verdict Complete and likely correct equality classification, but the proof rests on an unverified inequality from another preprint. read the letter →

arxiv 2608.04367 v1 pith:V2YDY6U3 submitted 2026-08-05 math.CO

Seyed Ahmad Mojallal This is my paper · ORCID

classification math.CO MSC 05C5005C35

keywords graphenergyindependencenumbervertexcoverextremalgraphscompletemultipartitespectraltheoryfractionalmatchingwell-covered

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

The paper determines exactly which graphs make the lower-bound inequality between adjacency energy $\mathcal E(G)$ and the independence number $\alpha(G)$, namely $\mathcal E(G)\ge 2(n-\alpha(G))$, an equality. It claims that every connected equality graph is either a single vertex, a balanced complete multipartite graph with at least two parts, or a graph $H_r(a,b)$ with $r\ge 3$ built by taking two balanced complete multipartite graphs with $r$ parts and completely joining corresponding parts; disconnected equality graphs are disjoint unions of these. The proof shows that equality is rigid enough to force every anti-neighborhood to be an equality graph and every edge to satisfy a tight numerical relation in the absolute adjacency matrix, then compresses the remaining structure into at most two algebraic classes. The payoff is a complete, checkable list of the extremal graphs, closing the equality problem for a spectral bound proposed in the 1980s.

What carries the argument

The machinery centers on the spectral decomposition $A=P-Q$ and the absolute adjacency matrix $B=P+Q=|A|$, the spectral-calculus absolute value of the adjacency matrix. Equality in the earlier proof's chain makes a local quantity $F_{uv}$ vanish on every edge, giving Lemma 3.1: for every edge $uv$, $B_{uu}=B_{vv}$ and $|B_{uv}|=B_{uu}-1$. The Gram representations $P_{xy}=\langle p_x,p_y\rangle$ and $Q_{xy}=\langle q_x,q_y\rangle$ then split edges into two types, either $p_u=p_v$ or $q_u=-q_v$. Vertices with equal $p$-vectors form P-classes, subdivided into cells with equal $q$-vectors; cell adjacencies are encoded by a weighted bipartite incidence graph whose matchings are exactly the independent sets. A uniform fractional matching and LP duality show that every P-class has exactly $R=n/\alpha$ cells of equal size, and the zero-sum identity $q_1+\cdots+q_R=0$ leaves only one or two P-classes, which are precisely the balanced complete multipartite and $H_R(a,b)$ cases.

What would settle it

Exact spectral enumeration of all connected graphs of order at most 10: compute $\mathcal E(G)$ and $\alpha(G)$ for each, and any graph with $\mathcal E(G)=2(n-\alpha(G))$ that is not a disjoint union of the three listed families would refute Theorem 1.3.

Watch

Extended reading notes

Core claim

The central claim, Theorem 1.3, is that $\mathcal E(G)=2(n-\alpha(G))$ holds if and only if every connected component of $G$ is an isolated vertex, a balanced complete multipartite graph $K_{a,a,\ldots,a}$ with at least two parts, or a graph $H_r(a,b)$ with $r\ge 3$ and $a,b\ge 1$. The graph $H_r(a,b)$ is formed from two balanced complete multipartite graphs, one with $r$ parts of size $a$ and one with $r$ parts of size $b$, by completely joining the $i$-th part of the first to the $i$-th part of the second for each $i$. The proof establishes necessity by showing that equality propagates to every anti-neighborhood, so the graph is well-covered, and then using the Gram vectors of the positive and negative spectral parts of the adjacency matrix to force a cell structure with at most two classes.

Load-bearing premise

The load-bearing premise is that the earlier inequality about anti-neighborhood energies and its local per-edge estimate are both correct, because every step of the equality proof uses them; if either were false, the classification would not follow.

Editorial extensions

If this is right

For any connected equality graph with $\alpha(G) < n/2$, the ratio $n/\alpha(G)$ is an integer.
A bipartite graph satisfies the equality if and only if every nontrivial component is a balanced complete bipartite graph.
The previously known examples $K_2\square K_r$ are exactly the case $H_r(1,1)$ inside the new family, so the earlier examples are covered and no further ones exist.
A disconnected graph attains equality exactly when each connected component does, so the connected classification is the whole classification.

Reading between the lines

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

A stability version is a natural extension not claimed in the paper: graphs with energy within $\epsilon$ of the bound should be close in edit distance to the listed families, since the rigidity lemmas are quantitative.
The integrality constraint $n/\alpha(G)\in\mathbb{Z}$ gives a cheap computational filter: any graph with $n/\alpha$ not an integer can be excluded from equality testing without computing its spectrum.
The same LP and Gram-vector machinery may characterize equality in other spectral lower bounds, such as the matching-number energy bound, where a different equality list is known but the method of proof here is transferable.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague,

The headline: this paper gives the first complete list of equality graphs for the energy–independence inequality E(G) ≥ 2(n−α(G)), and the list is very plausible. It is worth a close read if you work in spectral graph theory, though the proof leans on an external inequality that is still unpublished.

What is genuinely new: the H_r(a,b) family, and the proof that equality holds exactly for isolated vertices, balanced complete multipartite graphs, and that family. Earlier literature had only examples (K2□Kr and balanced complete multipartite graphs) plus partial bounds. The paper introduces a clean P-class/cell decomposition and reduces the cell adjacency structure to a weighted matching LP. That LP step is the most elegant part: a uniform fractional matching is shown to be optimal, and dual complementarity forces each P-class to have exactly R cells, all of the same size. The converse direction is handled properly—both families are verified by direct spectral computation, and the spectrum of H_r(a,b) is computed correctly.

The soft spot is the one flagged in the stress-test. Everything after Proposition 2.1 depends on inequality (5), 4|E(G)| + Σ E(G_v) ≤ n E(G), plus the F_uv ≥ 0 claim, both taken from Kumar–Pragada's preprint [8]. Neither is proved here. That is not a citation sin—the base inequality is the same authors' theorem—but it makes this paper's theorem conditional on an unpublished proof. A referee should verify [8, Lemma 2.2 and Claims 2.1/2.2] before signing off. Once (5) is granted, the combinatorial development is coherent; I did not find an internal gap.

Minor concerns: the notation is heavy but the structure is clear, and the literature review is honest about the partial results. The paper is a within-subfield contribution, not a breakthrough, but it closes a natural open question.

Who is this for: spectral graph theorists working on graph energy and extremal graph problems. It deserves a serious referee, not a desk reject. If [8] checks out, this should be accepted.

Recommendation: send to peer review, and ask the referee to verify the external inequalities—or have the author append a proof of (5).

Referee Report

2 major / 3 minor

Summary. The paper determines all finite simple graphs attaining equality in the recent Kumar–Pragada inequality E(G) ≥ 2(n − α(G)). The main result (Theorem 1.3) states that equality holds exactly when every connected component is an isolated vertex, a balanced complete multipartite graph K_{a,a,...,a}, or a member of the new family H_r(a,b) with r ≥ 3, obtained from two balanced complete r-partite graphs by completely joining corresponding parts (and adding no other cross-edges). The proof propagates equality to anti-neighborhoods, uses positive-semidefinite rigidity of the absolute adjacency matrix to derive a P-class/cell structure, encodes cell adjacencies in a weighted bipartite incidence graph, and uses weighted matching duality to show that at most two P-classes occur. The paper closes by verifying the spectra of the extremal families.

Significance. The equality case of the Graffiti/energy–independence conjecture is a natural and valuable contribution. If the supporting inequality from Kumar–Pragada is accepted, the classification is clean and the internal development from the P-class/cell construction onward is coherent. The spectral verification of the H_r(a,b) family is explicit and correct. The main weakness is that the initial equality propagation and edge rigidity depend on unproved technical facts from an unpublished preprint [8]; the paper is therefore conditional unless those facts are supplied or a published version is cited.

major comments (2)

[§2–§3, Eq. (5), Lemma 3.1] The proof of Theorem 1.3 is conditional on the external inequality (5) of Kumar and Pragada and on the accompanying Schur-complement/F_uv chain imported from [8, Claims 2.1/2.2]. Proposition 2.1 uses (5) to force equality in the summed anti-neighborhood bound, and Lemma 3.1 uses the unproved assertions that F_uv ≥ 0 and that the gap in the second inequality is exactly Σ_{uv∈E(G)} F_uv. Because [8] is an unpublished preprint, the characterization is not self-contained at a load-bearing point. Please either prove these supporting facts in the paper (for example, in an appendix) or cite a published/refereed version; at minimum, state the imported claims explicitly.
[§3, Lemma 3.1] The displayed lower bound for F_uv is algebraically incorrect. From F_uv = ((x−1)^2−z^2)/x + ((y−1)^2−z^2)/y = (x+y)/(xy)(xy+1−z^2)−4, the AM–GM bound x+y ≥ 2√(xy) gives F_uv ≥ (2/√(xy))((√(xy)−1)^2−z^2), not 2√(xy)((√(xy)−1)^2−z^2). The claimed conclusion (F_uv=0 implies x=y and (√(xy)−1)^2=z^2) still follows from the corrected bound, so this is repairable, but the current formula is false (e.g., x=y=100, z=0).

minor comments (3)

[§5.3, Figure 1] The example of the cell incidence graph is understandable in words; if the figure is omitted in the published version, the caption should be adjusted accordingly.
[§9, Corollary 9.2] The phrase 'contain triangles inside each of their two complete multipartite halves' is slightly imprecise; the triangles lie inside the X-side and the Y-side of H_r(a,b), not in the two P-classes as 'halves' in a geometric sense.
[References] Reference [8] is an arXiv preprint with a 2026 date; if a refereed or published version appears, it should be cited in its place so readers can verify the imported inequality.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the equality characterization is derived from an external inequality, not assumed, and the converse is verified by independent spectral computation.

full rationale

I walked the paper's derivation chain. The target is the equality case of an externally proved inequality E(G) >= 2(n - alpha(G)), so the paper does not need to prove the inequality itself. Proposition 2.1 assumes E(G)=2(n-alpha) and then applies the imported inequality (5) and the inequality (1) to anti-neighborhoods; this is legitimate use of a prior theorem, not circular definition. Lemma 3.1 derives edge rigidity from equality in the imported F_uv chain, and the later P-class/cell/matching arguments are internal combinatorial consequences of that rigidity. The converse is verified directly via spectra in Lemmas 7.1 and 7.2, independently of the classification. The main load-bearing premise, inequality (5) from Kumar and Pragada [8], is external and by different authors; dependence on an unverified external lemma is a correctness risk, not circularity. There is no self-citation chain, no fitted parameter renamed as a prediction, and no uniqueness claim imported from the present authors. The paper is therefore self-contained relative to its stated external input, and no specific reduction of a conclusion to its own premise is exhibited.

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

The paper's central claim rests on the recently proved energy-independence inequality and on specific lemmas from Kumar-Pragada's proof (inequality (5) and the F_uv chain). These are external results, not assumptions the paper itself introduces. No free parameters are fitted; the graph families are defined structurally. No new unobserved entities are postulated.

assumptions (6)

domain assumption Energy-independence inequality E(G) ≥ 2(n−α(G)) for all finite simple graphs (Kumar-Pragada theorem).
Proved in [8], used as the baseline throughout; the paper builds on it rather than reproving it.
domain assumption Key inequality 4|E(G)| + Σ_v E(G_v) ≤ |V(G)|E(G) for every graph.
Quoted from [8, Lemma 2.2]; it is the engine of equality propagation in Proposition 2.1.
domain assumption The F_uv nonnegativity chain used to control edge rigidity (Claims 2.1 and 2.2 of [8]).
Used in Lemma 3.1 to derive that every edge satisfies |B_uv| = B_uu − 1.
standard math Standard weighted matching theorem for bipartite graphs: ν_w(H) = ν*_w(H).
Used in Proposition 5.6 and Lemma 5.8; cited to Lovász-Plummer [10].
standard math Strong LP duality for the fractional matching and dual covering programs.
Used to derive complementary slackness (19) and (20).
standard math Standard spectrum of balanced complete multipartite graphs.
Used in Lemma 7.1; cited to Brouwer-Haemers [4].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Extremal Graphs for the Energy-Independence Number Inequality." pith.science (2026). https://pith.science/paper/V2YDY6U3

@misc{pith2026260804367,
  author       = {Pith},
  title        = {Pith review of: Extremal Graphs for the Energy-Independence Number Inequality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V2YDY6U3}},
  note         = {Machine review of arXiv:2608.04367}
}

abstract

For a graph $G$ of order $n$, let $\mathcal E(G)$ denote its adjacency energy and let $\alpha(G)$ denote its independence number. A recent theorem of Kumar and Pragada states that $$\mathcal E(G)\ge 2\bigl(n-\alpha(G)\bigr).$$ We determine all graphs attaining equality. More precisely, equality holds if and only if every connected component of $G$ is an isolated vertex, a balanced complete multipartite graph, or a graph obtained by taking the disjoint union of $K_{a,\ldots,a}$ and $K_{b,\ldots,b}$, with the same number $r\ge3$ of parts, and then completely joining corresponding parts.

Figures

Figures reproduced from arXiv: 2608.04367 by the authors.

**Figure 1.** A cell incidence graph. Each cell is represented by one weighted edge; antipodal cells [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 11 canonical work pages

[8]

Energy and independence number

H. Kumar and S. Pragada, Energy and independence number, preprint, arXiv:2607.19817 [math.CO], 2026. 17

work page Pith review arXiv 2026
[1]

A graph energy conjecture through the lenses of semidefinite programming

A. Abiad, G. Coutinho, E. Juliano, and L. Reijnders, A graph energy conjecture through the lenses of semidefinite programming, preprint, arXiv:2509.05814 [math.CO], 2025

work page Pith review arXiv 2025
[2]

Akbari, S

S. Akbari, S. K¨ u¸ c¨ uk¸ cif¸ ci, H. Saveh, and E.S ¸. Yazıcı, A lower bound for the energy of graphs in terms of the vertex cover number,Discrete Math.348 (2025), no. 11, 114582

work page 2025
[3]

Aouchiche and P

M. Aouchiche and P. Hansen, A survey of automated conjectures in spectral graph theory, Linear Algebra Appl.432 (2010), no. 9, 2293–2322

work page 2010
[4]

A. E. Brouwer and W. H. Haemers,Spectra of Graphs, Universitext, Springer, New York, 2012

2012
[5]

Chen and X

X. Chen and X. Liu, Remarks on the bounds of graph energy in terms of vertex cover number or matching number,Czechoslovak Math. J.71 (2021), no. 2, 309–319

work page 2021
[6]

Fajtlowicz, On conjectures of Graffiti

S. Fajtlowicz, On conjectures of Graffiti. II,Congr. Numer.60 (1987), 189–197

work page 1987
[7]

Gutman, The energy of a graph,Ber

I. Gutman, The energy of a graph,Ber. Math.-Statist. Sekt. Forschungszentrum Graz103 (1978), 1–22

work page 1978

Show all 12 references

[9]

Liu and B

L. Liu and B. Ning, Unsolved problems in spectral graph theory,Oper. Res. Trans.27 (2023), no. 4, 33–60

2023
[10]

Lov´ asz and M

L. Lov´ asz and M. D. Plummer,Matching Theory, North-Holland Mathematics Studies, vol. 121, North-Holland, Amsterdam, 1986

1986
[11]

Samanta, Improved bound of graph energy in terms of vertex cover number, preprint, arXiv:2507.00798 [math.CO], 2025

A. Samanta, Improved bound of graph energy in terms of vertex cover number, preprint, arXiv:2507.00798 [math.CO], 2025

2025 arXiv
[12]

Wang and X

L. Wang and X. Ma, Bounds of graph energy in terms of vertex cover number,Linear Algebra Appl.517 (2017), 207–216. 18

2017

Pith tools

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

[1] [8]

Energy and independence number

H. Kumar and S. Pragada, Energy and independence number, preprint, arXiv:2607.19817 [math.CO], 2026. 17

work page Pith review arXiv 2026

[2] [1]

A graph energy conjecture through the lenses of semidefinite programming

A. Abiad, G. Coutinho, E. Juliano, and L. Reijnders, A graph energy conjecture through the lenses of semidefinite programming, preprint, arXiv:2509.05814 [math.CO], 2025

work page Pith review arXiv 2025

[3] [2]

Akbari, S

S. Akbari, S. K¨ u¸ c¨ uk¸ cif¸ ci, H. Saveh, and E.S ¸. Yazıcı, A lower bound for the energy of graphs in terms of the vertex cover number,Discrete Math.348 (2025), no. 11, 114582

work page 2025

[4] [3]

Aouchiche and P

M. Aouchiche and P. Hansen, A survey of automated conjectures in spectral graph theory, Linear Algebra Appl.432 (2010), no. 9, 2293–2322

work page 2010

[5] [4]

A. E. Brouwer and W. H. Haemers,Spectra of Graphs, Universitext, Springer, New York, 2012

2012

[6] [5]

Chen and X

X. Chen and X. Liu, Remarks on the bounds of graph energy in terms of vertex cover number or matching number,Czechoslovak Math. J.71 (2021), no. 2, 309–319

work page 2021

[7] [6]

Fajtlowicz, On conjectures of Graffiti

S. Fajtlowicz, On conjectures of Graffiti. II,Congr. Numer.60 (1987), 189–197

work page 1987

[8] [7]

Gutman, The energy of a graph,Ber

I. Gutman, The energy of a graph,Ber. Math.-Statist. Sekt. Forschungszentrum Graz103 (1978), 1–22

work page 1978