Improved bound of graph energy in terms of vertex cover number

Aniruddha Samanta

REVIEW 5 major objections 6 minor 1 cited by

Improved bound of graph energy in terms of vertex cover number

T0 review · 5 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read For several graph families, energy is at least twice the vertex cover number, sharpening the known bound.

desk verdict Worth a serious referee, but Theorem 3.5's equality claim contradicts the paper's own Lemma 3.6 and the wheel proof uses a false inequality. read the letter →

arxiv 2507.00798 v1 pith:S7EQQ7AS submitted 2025-07-01 math.CO math.FA

Aniruddha Samanta This is my paper · ORCID

classification math.COmath.FA MSC 05C2205C5005C35

keywords graphenergyvertexcovernumbercycle-cliquegraphssplitwheeledgedeletioncutsetlowerbound

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 sets out to prove that for several broad families of graphs the adjacency energy $E(G)$ is at least twice the vertex cover number $\tau(G)$. This strengthens the established inequality $E(G) \geq 2\tau(G) - 2c(G)$, where $c(G)$ counts odd cycles, by removing the penalty term for many graphs. The families covered include cycle-clique graphs (graphs whose blocks are cycles or cliques), split graphs and their subclasses such as threshold graphs, wheel graphs $W_{m,n}$, bipartite graphs, complete graphs, and the Cartesian product $K_n \times K_2$. The arguments use induction on $\tau$ together with edge-deletion energy inequalities, and they also characterise the equality cases for connected cycle-clique graphs and for wheel graphs.

What carries the argument

The load-bearing mechanism is the pair of edge-deletion energy inequalities $E(G) \geq E(G-E)$ and, for a star-shaped cut set $E$, the strict version $E(G) > E(G-E)$, both quoted from the cited reference [2]. Combined with the block decomposition of cycle-clique graphs and the induction on $\tau$, these inequalities let the author reduce a graph to smaller components whose energies are already known to exceed twice their vertex cover numbers. For split graphs, the corresponding object is the VC-representation, a partition of the vertex set into a minimum vertex cover $X$ and an independent set $Y$, and the associated split graph obtained by making $X$ a clique; this transfers the bound from a complete graph to the original graph. The wheel computation additionally uses the explicit spectrum of $W_{m,n} = C_n \vee \overline{K_m}$, giving $E(W_{m,n}) = E(C_n) + 2\sqrt{mn+1} - 2$.

What would settle it

Compute $E(G)$ and $\tau(G)$ for the families covered, starting with small wheels such as $W_{2,4}$ and small cycle-clique graphs not in the equality list; if any has $E < 2\tau$, the bound is false, and the equality claim itself is falsified by a connected cycle-clique graph or a wheel outside the listed cases with $E = 2\tau$.

Watch

Extended reading notes

Core claim

The central claim is that the inequality $E(G) \geq 2\tau(G)$, already known for graphs with no odd cycles, actually holds for every cycle-clique graph, every split graph, every wheel graph $W_{m,n}$, and $K_n \times K_2$, among others. For connected cycle-clique graphs, equality holds only for $C_3$, $C_4$, a complete graph, an edge, or an isolated vertex; for wheels, equality holds exactly for $W_{1,3}$ and $W_{1,4}$. The proof for cycle-clique graphs proceeds by induction on $\tau$: when a pendent vertex exists, deleting its quasi-pendent neighbour lowers $\tau$ by exactly one, and a cut-set inequality shows the energy strictly exceeds the target; when no pendent vertex exists, a block tree is constructed and a suitable cut vertex in a leaf block is shown to lie in a minimum vertex cover, again reducing the problem to smaller pieces. For split graphs, the argument decomposes the graph into vertex-disjoint complete subgraphs whose vertex cover numbers add up to $\tau(G)$, together with the fact that deleting edges from a split graph to a clique cannot increase energy.

Load-bearing premise

The induction repeatedly assumes that a chosen cut vertex shared by several leaf blocks lies in some minimum vertex cover, so that deleting it lowers the vertex cover number by exactly one; if that fails for some graph, the reduction step breaks.

Editorial extensions

If this is right

Every cactus graph, friendship graph, block graph, and graph with vertex-disjoint cycles satisfies $E \geq 2\tau$, with equality only on the listed small graphs.
For split graphs, hence threshold graphs, nested split graphs, and complete split graphs, the energy is at least twice the vertex cover number.
For wheels $W_{m,n}$, the inequality $E \geq 2\tau$ holds for all $m,n$, and the only equality cases are the two smallest wheels $W_{1,3}$ and $W_{1,4}$.
For $K_n \times K_2$, the energy is exactly $2\tau$, matching the lower bound.
These results give a wide family of graphs with odd cycles where the odd-cycle penalty $2c$ in the Wang–Ma bound is unnecessary.

Reading between the lines

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

Editorial inference: If the block-induction strategy is sound, a natural next step is to test whether $E \geq 2\tau$ holds for all connected graphs, since the classes proven here already include many graphs with odd cycles.
Editorial inference: The equality characterisations suggest a broader pattern that equality should occur only for graphs whose energy is tight, typically built from bipartite or complete blocks; a computational search for other tight graphs would be a direct extension.
Editorial inference: The technique of switching to an associated split graph may extend the bound to any graph $G$ whose energy does not decrease when its vertex cover part is made into a clique; determining which graphs satisfy $E(G) \geq E(G_s)$ is a concrete open computational problem.
Editorial inference: The reliance on the cut-vertex-in-minimum-cover step hints that a counterexample to $E \geq 2\tau$, if one exists, would likely be a graph where every minimum vertex cover avoids a certain cut vertex; this gives a targeted search strategy.

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

Short version: the paper proves E(G) ≥ 2τ(G) for several graph families, improving the Wang–Ma bound E ≥ 2τ − 2c. The cycle-clique and split-graph results are real advances, and the K_n × K_2 example is fine. But the wheel theorem, Theorem 3.5, is wrong as stated. Its equality characterization conflicts with the paper's own Lemma 3.6, and the proof's inequality √(mn+1)−1 ≥ m fails for n < m+2. That section needs to be fixed before the results can be used.

What's genuinely new: Theorem 3.2 for cycle-clique graphs is the main contribution. The block-tree induction is a plausible approach, and the energy-comparison steps are standard. Theorem 3.4 for split graphs is clean and correctly uses vertex-disjoint complete subgraphs. The reduction of bipartite graphs to Wong's matching bound is immediate but correctly identified.

Soft spots, in order of seriousness. First, Theorem 3.5. Since E(W_{m,n}) = E(C_n) + 2√(mn+1) − 2, equality requires both E(C_n) = 2τ(C_n) and √(mn+1)−1 = m. For n = 4 the second equation forces m = 2, so W_{2,4} is an equality case and W_{1,4} is not; the theorem claims the opposite. Also the proof's universal inequality √(mn+1)−1 ≥ m is false, e.g. m = 2, n = 3 gives √7−1 ≈ 1.65 < 2. So the wheel inequality is not established in the τ(W_{m,n}) = n regime, even though spot checks suggest it may be true. Second, Theorem 3.2 assumes without proof that a cut vertex shared by leaf blocks and a parent block lies in some minimum vertex cover. That is not true for arbitrary block trees (a path P5 has a cut vertex in none of its minimum covers), so a proof is needed in the specific cycle-clique setting. Third, Lemma 3.2 asserts a five-structure classification with no proof beyond a figure. Fourth, the split-graph proof has a missing theorem reference ('by Theorem' with no number), and Proposition 3.3/Theorem 3.7 seem to need n ≥ 2 for the cited lemma.

Bottom line: the paper is worth a serious look because the main inequalities for cycle-clique and split graphs are plausible and the literature use is honest. But the current form has load-bearing errors in the wheel section and several unproved structural claims. I'd send it to peer review, but the revision must fix the equality cases, repair the wheel proof, and supply the missing arguments. This is for specialists in graph energy; I wouldn't cite the arXiv version until the wheel part is corrected.

Referee Report

5 major / 6 minor

Summary. The paper aims to prove the lower bound E(G) >= 2*tau(G) for several graph classes, improving the known Wang-Ma bound E(G) >= 2*tau(G) - 2c, where c is the number of odd cycles. The classes treated include complete graphs, bipartite graphs, cycles, trees, cycle-clique graphs, split graphs, wheel graphs W_{m,n}, and Cartesian products K_n x K_2. For several of these classes the paper also states equality characterizations. The main tools are known comparison theorems for graph energy under edge deletion (Day-So), the Wong-Wang-Chu matching bound, and the Wang-Ma vertex-cover bound, together with structural decompositions of the relevant graph classes. The central result for wheels, Theorem 3.5, is incorrect as stated, and the proof of the broad cycle-clique theorem contains significant unproved structural steps.

Significance. If the results were correct, the paper would give a clean improvement of the Wang-Ma bound for several natural families, and the equality characterizations would be useful. The paper draws on external theorems rather than fitted parameters, and the statements are falsifiable. However, the paper's most prominently claimed equality case, Theorem 3.5, is demonstrably false: the family W_{m,n} has additional equality cases and one of the claimed equality cases fails. This is a load-bearing error. The induction proof for cycle-clique graphs also relies on assertions about minimum vertex covers containing specified cut vertices and on an unproved classification of graphs with vertex cover number 2. These issues require nontrivial repair, but the underlying approach is plausible and the other listed families may still satisfy the claimed inequality after correction.

major comments (5)

[Section 3, Theorem 3.5] The equality characterization in Theorem 3.5 is false. By Lemma 3.6, E(W_{m,n}) = E(C_n) + 2*sqrt(mn+1) - 2, and tau(W_{m,n}) = tau(C_n) + m when m <= floor(n/2). For n=4 and m=1, E(W_{1,4}) = 4 + 2*sqrt(5) - 2 is about 6.47, while 2*tau(W_{1,4}) = 2*(2+1) = 6, so W_{1,4} is not an equality case. For n=4 and m=2, E(W_{2,4}) = 4 + 2*sqrt(9) - 2 = 8 and 2*tau(W_{2,4}) = 2*(2+2) = 8, so W_{2,4} is an equality case omitted by the theorem. The 'if and only if' statement must be corrected, and the equality analysis in the proof is incomplete.
[Section 3, proof of Theorem 3.5] The proof asserts 'for any n>=3, sqrt(mn+1)-1 >= m'. This inequality is false when n < m+2. For example, m=2 and n=3 give sqrt(7)-1, which is about 1.65 and is strictly less than 2. The displayed chain of inequalities therefore does not establish E(W_{m,n}) >= 2*tau(W_{m,n}) in the regime tau(W_{m,n}) = n, since the step 2*sqrt(mn+1)-2 >= 2m fails there. A different argument is needed for that case.
[Section 3, Lemma 3.2 and Theorem 3.2] The statement that every graph with vertex cover number 2 has one of the five structures in Figure 1 is asserted without proof, and the figure captions do not give precise definitions of the parameters and edge sets. This classification is used as the base case of the induction in Theorem 3.2 and is load-bearing. A rigorous proof or a precise citation is required.
[Section 3, Theorem 3.2, Cases 2.1 and 2.2] The proof repeatedly uses the assertions that 'there is a minimum vertex cover U of G such that u1 in U' and 'tau(G-u1) = tau(G)-1' for a cut vertex shared by several leaf blocks and the parent block. No proof is supplied. While such a claim can be proved for leaf cycles and leaf cliques by replacing vertices in each block, the argument is not immediate and the induction depends on it. Additionally, the sentence 'Then similar to Case 2.1.1' refers to a case that is not defined anywhere in the text.
[Section 3, Theorem 3.4] In the tau(G) = p case, the proof states 'so by Theorem and E(G) >= sum_i E(G_i)' without naming the theorem used. The inequality is true for vertex-disjoint induced subgraphs because the trace norm of the adjacency matrix dominates the trace norm of the direct sum of the corresponding principal submatrices after deleting cross edges, but this step should be stated and justified explicitly rather than left as an unnamed reference.

minor comments (6)

[Section 3, Proposition 3.1] For bipartite graphs the proof says the claim is 'easy to observe'; this uses Konig's theorem to identify tau(G) with the matching number and the Wong-Wang-Chu bound E(G) >= 2*mu(G), and should be stated explicitly.
[Section 3, Theorem 3.1] The displayed 'S_n = 2*sqrt(n)' should read E(S_n) = 2*sqrt(n-1) for the star with n vertices.
[Section 3, Lemma 3.6] The spectrum of W_{m,n} is cited as a 'known result' without a reference or derivation. A citation should be added.
[Section 3, Theorem 3.3] The statement 'If G is isomorphic to C_n, for n > 5, then E(C_n) > 2*tau(C_n)' should probably say n >= 5, since C_5 also satisfies strict inequality while the equality cases listed later omit C_5.
[Section 3, Theorem 3.6] Theorem 3.6 is conditional on the hypothesis E(G) >= E(G_s) for some associated split graph, but no concrete class of graphs is shown to satisfy this hypothesis. As stated, it establishes the bound only for graphs already covered by the condition and does not by itself prove the result for any new family.
[Throughout] There are several typographical and notational issues: 'G prime s', 'B prime s', 'by Theorem' with no theorem number, and references to 'Case 2.1.1' that do not correspond to a numbered case. These should be cleaned up during revision.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the energy bounds are obtained from independent external theorems; the only self-citation is a non-load-bearing bibliographic pointer.

full rationale

I walked the derivation chain for each theorem. The bound E(G) ≥ 2τ(G) is never assumed as the thing being proved. Theorem 3.1 uses Day–So's energy-decrease under edge deletion (Theorems 2.2–2.3) plus induction on trees; Theorem 3.2 inducts on τ with base cases from Proposition 3.1 and Lemma 3.3; Theorem 3.4 reduces split graphs to complete graphs via the Day–So cut-set machinery and Lemma 3.5; Theorem 3.6 is a conditional reduction to split graphs; Theorem 3.7 invokes Bapat's spectral formula. The external inputs (Wang–Ma, Wong et al., Day–So, Bapat) are independent of the paper's claims. The only self-citation is in the introduction, 'Later, many authors extended results (1) and (2) ... see references [3]', and it supports no theorem, so it is not load-bearing. I did, however, find non-circular correctness gaps: Theorem 3.5's proof asserts 'for any n ≥ 3, √(mn+1)−1 ≥ m', which fails when n < m+2, and its equality characterization omits W_{2,4} while including W_{1,4}; several induction steps also assert without proof the existence of a minimum vertex cover containing a chosen cut vertex. These are mathematical gaps, not instances of a prediction or bound reducing to its own inputs, so they do not raise the circularity score beyond the minor self-citation level.

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

The central claim rests on standard spectral graph theory facts and on four external theorems (Day-So, Wong, Wang-Ma, Bapat). One internally introduced structural assertion (Lemma 3.2) is unproved, and the vertex-cover reduction for cut vertices is a domain assumption. No fitted parameters and no invented entities appear.

assumptions (7)

standard math Known inequality E(G) ≥ 2μ(G) for matching number μ (Wong et al. [5])
Used in Proposition 3.1 for bipartite graphs and even cycles, and implicitly in the tree argument where τ = μ.
standard math Cut-set energy inequalities of Day and So [2]: E(G) ≥ E(G−E) for a simple cut set, and strict inequality for a star cut set
These are the primary tools in Lemma 3.1, Theorem 3.1, and Theorem 3.2.
standard math Cycle energy formulas in Lemma 2.1
Used to prove the odd-cycle case in Proposition 3.1 and in the wheel graph computation.
standard math Bapat [1, Lemma 3.26] gives the spectrum and energy of K_n × K_2
Used in Theorem 3.7 to obtain E(K_n × K_2) = 4(n−1).
ad hoc to paper Every graph with vertex cover number 2 has one of the five structures in Figure 1
Asserted without proof in Lemma 3.2; load-bearing for the base case of the cycle-clique theorem.
domain assumption For a cut vertex u1 in a cycle-clique graph without pendent vertices, there exists a minimum vertex cover containing u1, and τ(G−u1) = τ(G)−1
Stated in Lemma 3.4 and Theorem 3.2 without full justification; the induction step depends on it.
standard math Energy of a graph is at least the sum of energies of vertex-disjoint induced subgraphs
Invoked in Theorem 3.4 for split graphs; follows from singular value interlacing but is not proved in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Improved bound of graph energy in terms of vertex cover number." pith.science (2026). https://pith.science/paper/S7EQQ7AS

@misc{pith2026250700798,
  author       = {Pith},
  title        = {Pith review of: Improved bound of graph energy in terms of vertex cover number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S7EQQ7AS}},
  note         = {Machine review of arXiv:2507.00798}
}

abstract

Let $ G $ be a simple graph with the vertex cover number $ \tau $. The energy $ \mathcal{E}(G) $ of $ G $ is the sum of the absolute values of all the adjacency eigenvalues of $ G $. In this article, we establish $ \mathcal{E}(G)\geq 2\tau $ for several classes of graphs. The result significantly improves the known result $ \mathcal{E}(G)\geq 2\tau-2c$ for many classes of graphs, where $ c $ is the number of odd cycles.

Figures

Figures reproduced from arXiv: 2507.00798 by the authors.

**Figure 2.** Graphs Gp,q and Dp,q 5 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** Graph G Let us denote G − C by an induced subgraph of G with vertices V (G) \ V (C), where C is a cycle in G. For an edge e ∈ E(G), G − e is obtained from G by removing e. Lemma 3.4. If G is a cactus graph with all blocks being cycles and exactly one cut vertex v (see [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Graphs W1,4 and W1,3 Some particular type of split graphs are threshold graphs, nested split graph, complete split graph etc. Corollary 3.4. If G is a threshold graph, then E(G) ≥ 2τ (G). A graph obtained by joining a vertex u to every vertex of a cycle Cn is known as …

**Figure 5.** Figure 5: Graph G and its VC-Representation Definition 3.2. Let G be a connected graph with a minimum vertex cover X. An associated split graph of G, denoted by Gs, is obtained by adding some edges in G such that the resulting subgraph induced by X forms a clique. It is to be ob…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Extremal Graphs for the Energy-Independence Number Inequality
math.CO 2026-08 accept novelty 7.0 of 10

The equality graphs for the energy-independence inequality are exactly disjoint unions of isolated vertices, balanced complete multipartite graphs, and the new family H_r(a,b).

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages · cited by 1 Pith paper

[1]

R. B. Bapat, Graphs and matrices, Universitext, Springer, London; Hindustan Book Agency, New Delhi, 2010

work page 2010
[2]

428 (2008), no

ane Day and Wasin So, Graph energy change due to edge deletion, Linear Algebra Appl. 428 (2008), no. 8-9, 2070–2078. 12

work page 2008
[3]

612 (2021), 1–29

Aniruddha Samanta and M Rajesh Kannan, Bounds for the energy of a complex unit gain graph, Linear Algebra and its Appl. 612 (2021), 1–29

work page 2021
[4]

517 (2017), 207–216

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

work page 2017
[5]

549 (2018), 276–286

Dein Wong, Xinlei Wang, and Rui Chu, Lower bounds of graph energy in terms of matching number, Linear Algebra Appl. 549 (2018), 276–286. 13

work page 2018

Pith tools

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

[1] [1]

R. B. Bapat, Graphs and matrices, Universitext, Springer, London; Hindustan Book Agency, New Delhi, 2010

work page 2010

[2] [2]

428 (2008), no

ane Day and Wasin So, Graph energy change due to edge deletion, Linear Algebra Appl. 428 (2008), no. 8-9, 2070–2078. 12

work page 2008

[3] [3]

612 (2021), 1–29

Aniruddha Samanta and M Rajesh Kannan, Bounds for the energy of a complex unit gain graph, Linear Algebra and its Appl. 612 (2021), 1–29

work page 2021

[4] [4]

517 (2017), 207–216

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

work page 2017

[5] [5]

549 (2018), 276–286

Dein Wong, Xinlei Wang, and Rui Chu, Lower bounds of graph energy in terms of matching number, Linear Algebra Appl. 549 (2018), 276–286. 13

work page 2018