Spectral radius of graphs of given size with forbidden a fan graph $F_6$

Jing Gao; Xueliang Li

REVIEW 2 major objections 3 minor 22 references

Spectral radius of graphs of given size with forbidden a fan graph $F_6$

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

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

Pith's one-line read For $m \geq 88$, every $F_6$-free graph has spectral radius at most $(1+\sqrt{4m-3})/2$, attained exactly by the book graph $K_2 \vee ((m-1)/2)K_1$.

desk verdict The F6 case is genuinely solved for odd m, but the theorem as stated overclaims even m and the component classification needs a real proof or citation. read the letter →

arxiv 2412.13792 v1 pith:B5OVO464 submitted 2024-12-18 math.CO

Jing Gao , Xueliang Li This is my paper · ORCID

classification math.CO MSC 05C3505C50

keywords spectralradiusfangraphF6-freeextremalPerronvectorP5-freeBrualdi–Hoffman–Turánproblem

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 settles the last open case of a spectral Turán conjecture for fan graphs, proving an exact upper bound on the spectral radius of any graph with $m \geq 88$ edges that contains no copy of $F_6$, the fan graph formed by joining a new vertex to a path on five vertices. The bound is $\lambda(G) \leq (1+\sqrt{4m-3})/2$, and equality holds exactly when $G$ is a book graph: two adjacent universal vertices joined to $(m-1)/2$ isolated vertices. This matters because it completes the conjecture for all fan graphs $F_k$, showing that the same family of complete split graphs is extremal in the one remaining case, $k=2$. The proof is an extremal-graph analysis using the Perron vector of the adjacency matrix.

What carries the argument

The proof's load-bearing device is a partition of the extremal graph $G^*$ at a vertex $u^*$ of maximal Perron coordinate: $U$ is the neighborhood of $u^*$, $W$ is the remaining vertices, and Perron-vector inequalities yield a key counting inequality that bounds the number of edges inside $W$. A second critical ingredient is Lemma 3.2, which classifies every connected component of $G^*[U]$ — necessarily $P_5$-free — as exactly one of six types: a star, a double star, a star with one added edge ($K_{1,r}+e$), $C_4$, $K_4-e$, or $K_4$. The subsequent lemmas eliminate all component types except stars, forcing the whole graph into the split form $K_2 \vee ((m-1)/2)K_1$. The Perron-vector edge-shift lemma, which transfers edges toward higher-coordinate vertices and strictly increases the spectral radius, drives the elimination arguments.

What would settle it

A concrete way to test the theorem is computational: for each $m$ from 88 up to, say, 200, enumerate or sample $F_6$-free graphs with $m$ edges, compute their spectral radii, and check that none exceeds $(1+\sqrt{4m-3})/2$ and that the only graphs attaining it are isomorphic to $K_2 \vee ((m-1)/2)K_1$. An alternative structural check is to exhibit an $F_6$-free graph whose neighborhood subgraph at some vertex has a connected $P_5$-free component that is not a star, double star, $K_{1,r}+e$, $C_4$, $K_4-e$, or $K_4$, which would falsify Lemma 3.2.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: if $G$ is $F_6$-free and has $m \geq 88$ edges, then its spectral radius $\lambda(G)$ is at most $(1+\sqrt{4m-3})/2$, and this value is attained exactly by the graph $K_2 \vee ((m-1)/2)K_1$, a clique of two vertices whose common neighborhood is an independent set of size $(m-1)/2$. This confirms the $k=2$ case of the earlier conjecture that, for sufficiently many edges, $F_{2k+1}$-free and $F_{2k+2}$-free graphs have spectral radius bounded by $(k-1+\sqrt{4m-k^2+1})/2$, with equality only on $K_k$ joined to an independent set.

Load-bearing premise

The proof relies on Lemma 3.2, which states that every component of the neighborhood-induced subgraph $G^*[U]$ must belong to one of six listed graph families; this classification is borrowed from another paper with only a 'similarly' argument, and every subsequent elimination step enumerates exactly those six possibilities, so if the classification misses a possible component, the proof does not cover all $F_6$-free graphs.

Editorial extensions

If this is right

The spectral Turán conjecture for fan graphs is now settled for every $k \geq 2$, closing the $k=2$ gap left by the earlier unified proof for $k \geq 3$.
Any $F_6$-free graph with $m \geq 88$ edges and spectral radius greater than $(1+\sqrt{4m-3})/2$ must contain a fan $F_6$ as a subgraph, so the bound is a sharp spectral-forcing threshold.
The extremal graph is unique up to isomorphism: $K_2 \vee ((m-1)/2)K_1$, a clique of two vertices joined to an independent set of $(m-1)/2$ vertices.
For $m \geq 88$, the bound implies $\lambda(G) \leq \sqrt{m} + 1/2$, an asymptotic form useful for quick estimates.

Reading between the lines

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

If Lemma 3.2's six-type classification is made fully self-contained, the rest of the proof requires only the Perron-vector shift lemma and elementary counting, so the argument could be re-exposed as a standalone proof for $F_6$.
The same partition-and-classify strategy could in principle be adapted to the remaining small fan graphs $F_7$ or $F_8$, provided the corresponding neighborhood subgraph classification is worked out.
Computational searches for $m$ between roughly 20 and 87 could show whether the book graph remains extremal below the paper's threshold of 88, which the proof's constants suggest is not optimal.

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

Gao and Li close the F6 gap in Yu et al.'s spectral Turán conjecture, and for odd m the proof looks sound. The Perron-vector framework is applied carefully: inequality (1) is derived from the eigenvector equations, the threshold λ>49/5 controls the arithmetic, and the elimination of K4, K4−e, C4, K1,r+e components forces the extremal graph to be K2∨((m−1)/2)K1. I checked the main estimates in Lemmas 3.1–3.4 and the final star/double-star step; nothing circular jumps out, and the bound is not fitted to the target.

The soft spots are real but fixable. First, Theorem 1.2 states m≥88 with no parity condition, but the extremal graph K2∨((m−1)/2)K1 exists only for odd m. The proof opens by using this graph to get the lower bound λ(G*)≥(1+√(4m−3))/2, so for even m the argument has no starting object and the claimed theorem is not proved. The last line of the proof even derives m=2r+1, so the argument only covers odd m. The statement should either restrict to odd m (m=2s+1, s≥44) or give a separate argument for even m.

Second, Lemma 3.2, which classifies every component of G*[U] as a star, double star, K1,r+e, C4, K4−e, or K4, is borrowed without proof ('Similarly to Lemma 4.5 in [8]'). Every later elimination depends on this list being exhaustive. It is probably true, and a precise citation to the exact statement in [8] might be enough, but as written the provenance is too vague for a lemma that carries the proof.

Minor: the equality statement in the abstract repeats the same half-integer issue, and the notation (m−1)/2 K1 should be made unambiguous.

Overall: the odd-m result is a genuine completion of the last open case, and the proof is a serious piece of work. With the parity hypothesis fixed and Lemma 3.2 properly sourced, I would take it. For peer review, yes—send it to a referee; the referee should focus on the parity restriction and the classification lemma.

Referee Report

2 major / 3 minor

Summary. The paper studies the spectral radius of F6-free graphs with a fixed number of edges m, where F6 is the fan graph K1 ∨ P5. The main result, Theorem 1.2, claims that for every m ≥ 88, every F6-free graph G with m edges satisfies λ(G) ≤ (1 + √(4m−3))/2, with equality if and only if G ≅ K2 ∨ ((m−1)/2)K1. The proof takes an extremal graph G*, uses the Perron vector to derive a key inequality (1), and then analyzes the induced subgraph G*[U] on the neighborhood of a maximal Perron-coordinate vertex u*. After proving e(U) ≥ 4, the authors classify the components of G*[U] into six types, show γ(H) ≤ 0 for every nontrivial component, and then successively eliminate K4, K4−e, C4, and K1,r+e components, leaving only stars and double stars. A final argument forces the unique nontrivial component to be a star and W to be empty, yielding the extremal graph K2 ∨ ((m−1)/2)K1. The paper thus claims to resolve the remaining k = 2 case of a conjecture of Yu et al. on fan-free graphs.

Significance. If Theorem 1.2 is correct, the paper closes the last open case of a natural spectral Turán-type conjecture for fan graphs, complementing the recently proved cases k ≥ 3 by Li et al. The proof is a substantial, mostly self-contained case analysis built on the Perron-vector method, and the numerical thresholds (λ > 49/5, e(W) ≤ 1, etc.) are derived from the stated inequalities rather than fitted to the conclusion. The paper also gives an explicit extremal construction and identifies the unique extremal graph. The main significance is therefore conditional on two points that need attention: the well-definedness of the extremal graph and the validity of the component classification. The proof does not appear to be circular; the central bound is derived from the Perron-vector equations, and the cited references are used for supporting structural facts, not for the main F6 bound itself.

major comments (2)

[Theorem 1.2] The theorem as stated is not well-defined for even m. For even m, (m−1)/2 is not an integer, so the graph K2 ∨ ((m−1)/2)K1 does not exist and the equality condition is not a well-formed graph isomorphism. The proof also uses this graph at the outset to assert λ(G*) ≥ (1+√(4m−3))/2, which yields the crucial inequalities λ²−λ ≥ m−1 and λ > 49/5. For even m this lower bound cannot be invoked. Moreover, the final step of the proof concludes m = 2r+1, so the argument as written only covers odd m. The theorem, the abstract, and the proof need either an explicit hypothesis that m is odd, or a separate treatment of even m showing that the upper bound still holds (and that equality is impossible). This is a load-bearing issue because every later estimate in the proof relies on the initial lower bound.
[Lemma 3.2] Lemma 3.2 classifies every component of G*[N(u)] into six types (star, double star, K1,r+e, C4, K4−e, K4), but the proof is not given; the text says only 'Similarly to the proof of Lemma 4.5 in [8]' without stating the referenced lemma or explaining how it applies to P5-free induced neighborhoods. This classification is load-bearing: Lemmas 3.8, 3.9, 3.11, and 3.14 eliminate components by enumerating exactly these six types, and the final structural conclusion depends on the classification being complete. If the classification is incomplete or the hypotheses of the referenced result are not met, the proof does not cover all F6-free graphs. The authors should either provide a self-contained proof of Lemma 3.2 or give a precise statement of the relevant result from [8] and verify its applicability here.

minor comments (3)

[Lemma 3.1] The displayed inequality 'λ > √m + 3' appears to be a typesetting error; from λ ≥ (1+√(4m−3))/2 one can derive λ > √(m+3) for m ≥ 88, but not λ > √m + 3 (which is false for m = 88). Please correct the square-root notation in this line.
[Introduction, Conjecture 1.1] The conjecture as quoted has the same integrality issue: the expression m/k − (k−1)/2 is not an integer for general m, so the extremal graph K_k ∨ (m/k − (k−1)/2)K1 is not always defined. Clarify the intended arithmetic condition (e.g., m ≡ k(k−1)/2 mod k) in the conjecture and in the abstract.
[Section 3] The equality condition of inequality (2) states that equality holds if and only if λ²−λ = m−1 and xw = xu* for every w ∈ W with dU(w) ≥ 1; this condition is used later in Lemma 3.10 and in the final star analysis, so it would help to display it as a numbered equation for easier reference.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the spectral bound is derived from Perron-vector equations and independent structural lemmas, not from the conjecture or from self-citation.

full rationale

The paper proves Theorem 1.2 by taking an extremal F6-free graph G*, writing the Perron-vector equations, and deriving inequalities (1)-(2) directly from λ^2−λ ≥ m−1. The lower bound λ(G*) ≥ λ(K2∨((m−1)/2)K1) uses only the fact that this explicit graph is F6-free and has m edges; it does not assume the target inequality. Lemmas 3.3-3.14 bound the component contributions γ(H) through elementary degree-counting and F6-freeness arguments, and the final proof eliminates K4, K4−e, C4, and K1,r+e components until only stars and double-stars remain. The only imported structural fact, Lemma 3.2, is cited to Liu-Wang [8], not to the authors' own work, and it is used as an external classification lemma rather than as a restatement of Theorem 1.2. The citation [5] supplies the k≥3 case of the conjecture as context, not as the F6 bound. No parameter is fitted to data, and no equality case is assumed. The even-m well-definedness issue noted for m even is a correctness concern about the theorem statement, not a circularity of the derivation.

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

The paper introduces no free parameters or invented entities. All external inputs are standard prior lemmas in spectral graph theory; the main load-bearing borrowed result is the component classification of P5-free graphs (Lemma 3.2), which is not proved in the text.

assumptions (6)

standard math Perron-Frobenius theorem: a connected graph has a positive eigenvector for its spectral radius.
Used in the proof of Theorem 1.2 to define the Perron vector x and its maximal coordinate u*.
standard math Lemma 2.1 (Nosal): every K3-free graph with m edges has spectral radius at most sqrt(m).
Used in the final step to rule out bipartite extremal graphs by comparing sqrt(m) with (1+sqrt(4m-3))/2.
standard math Lemma 2.2 (Wu, Xiao, Hong): rotating edges to a vertex with larger Perron coordinate strictly increases the spectral radius.
Used repeatedly to show the extremal graph would be improved by moving edges, forcing the neighbor structure of u*.
domain assumption Lemma 2.3 (Zhai, Lin, Shu): for a 2-connected forbidden subgraph, in a maximum spectral radius graph in G(m,F), all vertices outside the closed neighborhood of an extremal vertex have degree at least 2.
Ensures the graph G* is connected, has no isolated vertices, and vertices in W have neighbors in U, which is used in Lemma 3.10 and later.
standard math Lemma 2.4 (Li, Zhao, Zou): in an F_k-free graph, the neighborhood of any vertex is P_{k-1}-free.
Gives the P5-free property of G*[U], which is the basis for the component classification in Lemma 3.2. This is an easy consequence but cited rather than proved.
domain assumption Lemma 3.2 classification of components of a P5-free graph (from Liu and Wang, Lemma 4.5 in [8]).
The set of possible components of G*[U] is asserted without proof in this paper; it is load-bearing because all later eliminations enumerate these types.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Spectral radius of graphs of given size with forbidden a fan graph $F_6$." pith.science (2026). https://pith.science/paper/B5OVO464

@misc{pith2026241213792,
  author       = {Pith},
  title        = {Pith review of: Spectral radius of graphs of given size with forbidden a fan graph $F_6$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/B5OVO464}},
  note         = {Machine review of arXiv:2412.13792}
}

abstract

Let $F_k=K_1\vee P_{k-1}$ be the fan graph on $k$ vertices. A graph is said to be $F_k$-free if it does not contain $F_k$ as a subgraph. Yu et al. in [arXiv:2404.03423] conjectured that for $k\geq2$ and $m$ sufficiently large, if $G$ is an $F_{2k+1}$-free or $F_{2k+2}$-free graph, then $\lambda(G)\leq \frac{k-1+\sqrt{4m-k^2+1}}{2}$ and the equality holds if and only if $G\cong K_k\vee\left(\frac{m}{k}-\frac{k-1}{2}\right)K_1$. Recently, Li et al. in [arXiv:2409.15918] showed that the above conjecture holds for $k\geq 3$. The only left case is for $k=2$, which corresponds to $F_5$ or $F_6$. Since the case of $F_5$ was solved by Yu et al. in [arXiv:2404.03423] and Zhang and Wang in [On the spectral radius of graphs without a gem, Discrete Math. 347 (2024) 114171]. So, one needs only to deal with the case of $F_6$. In this paper, we solve the only left case by determining the maximum spectral radius of $F_6$-free graphs with size $m\geq 88$, and the corresponding extremal graph.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 17 canonical work pages

[8]

Y. Liu, L. Wang, Spectral radius of graphs of given size with forb idden subgraphs, Linear Algebra Appl. 689 (2024) 108–125

work page 2024
[1]

Bondy, U

J. Bondy, U. Murty, Graph Theory, Springer, New York, 2008

work page 2008
[2]

Brualdi, A

R. Brualdi, A. Hoﬀman, On the spectral radius of (0,1)-matrices , Linear Algebra Appl. 65 (1985) 133–146

work page 1985
[3]

Cvetkovi´ c, P

D. Cvetkovi´ c, P. Rowlinson, S. Simi´ c, An Introduction to theTheory of Graph Spectra, Cambridge University Press, New York, 2010

work page 2010
[4]

X. Fang, L. You, The maximum spectral radius of graphs of given size with forbidden subgraph, Linear Algebra Appl. 666 (2023) 114–128

work page 2023
[5]

S. Li, S. Zhao, L. Zou, Spectral extrema of graphs with ﬁxed siz e: forbidden fan graph, friendship graph or theta graph, arXiv:2409.15918

arXiv
[6]

Y. Li, L. Lu, Y. Peng, Spectral extremal graphs for the bowtie , Discrete Math. 346 (2023) 113680

work page 2023
[7]

H. Lin, B. Ning, B. Wu, Eigenvalues and triangles in graphs, Comb. P robab. Comput. 30 (2021) 258–270

work page 2021

Show all 22 references

[9]

J. Lu, L. Lu, Y. Li, Spectral radius of graphs forbidden C7 or C △ 6 , Discrete Math. 347 (2024) 113781

2024
[10]

G. Min, Z. Lou, Q. Huang, A sharp upper bound on the spectral radius of C5-free/C6- free graphs with given size, Linear Algebra Appl. 640 (2022) 162–17 8

2022
[11]

Nikiforov, Some inequalities for the largest eigenvalue of a gra ph, Combin

V. Nikiforov, Some inequalities for the largest eigenvalue of a gra ph, Combin. Probab. Comput. 11 (2002) 179–189

2002
[12]

Nikiforov, Walks and the spectral radius of graphs, Linear A lgebra Appl

V. Nikiforov, Walks and the spectral radius of graphs, Linear A lgebra Appl. 418 (2006) 257–268

2006
[13]

Nikiforov, The maximum spectral radius of C4-free graphs of given order and size, Linear Algebra Appl

V. Nikiforov, The maximum spectral radius of C4-free graphs of given order and size, Linear Algebra Appl. 430 (2009) 2898–2905

2009
[14]

Nikiforov, On a theorem of Nosal, arXiv:2104.12171

V. Nikiforov, On a theorem of Nosal, arXiv:2104.12171. 20

arXiv
[15]

Nosal, Eigenvalues of graphs, Master’s thesis, University of Calgary, 1970

E. Nosal, Eigenvalues of graphs, Master’s thesis, University of Calgary, 1970

1970
[16]

W. Sun, S. Li, W. Wei, Extensions on spectral extrema of C5/C 6-free graphs with given size, Discrete Math. 346 (2023) 113591

2023
[17]

Wang, Generalizing theorems of Nosal and Nikiforov: Triangle s and quadrilaterals, Discrete Math

Z. Wang, Generalizing theorems of Nosal and Nikiforov: Triangle s and quadrilaterals, Discrete Math. 345 (2022) 112973

2022
[18]

B. Wu, E. Xiao, Y. Hong, The spectral radius of trees on k pendant, Linear Algebra Appl. 395 (2005) 343–349

2005
[19]

L. Yu, Y. Li, Y. Peng, Spectral extremal graphs for fan grap hs, arXiv:2404.03423

arXiv
[20]

M. Zhai, H. Lin, J. Shu, Spectral extrema of graphs with ﬁxed s ize: cycles and complete bipartite graphs, European J. Combin. 95 (2021) 103322

2021
[21]

M. Zhai, J. Shu, A spectral version of Mantel’s theorem, Discre te Math. 345 (2022) 112630

2022
[22]

Zhang, L

Y. Zhang, L. Wang, On the spectral radius of graphs without a gem, Discrete Math. 347 (2024) 114171. 21

2024

Pith tools

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

[1] [8]

Y. Liu, L. Wang, Spectral radius of graphs of given size with forb idden subgraphs, Linear Algebra Appl. 689 (2024) 108–125

work page 2024

[2] [1]

Bondy, U

J. Bondy, U. Murty, Graph Theory, Springer, New York, 2008

work page 2008

[3] [2]

Brualdi, A

R. Brualdi, A. Hoﬀman, On the spectral radius of (0,1)-matrices , Linear Algebra Appl. 65 (1985) 133–146

work page 1985

[4] [3]

Cvetkovi´ c, P

D. Cvetkovi´ c, P. Rowlinson, S. Simi´ c, An Introduction to theTheory of Graph Spectra, Cambridge University Press, New York, 2010

work page 2010

[5] [4]

X. Fang, L. You, The maximum spectral radius of graphs of given size with forbidden subgraph, Linear Algebra Appl. 666 (2023) 114–128

work page 2023

[6] [5]

S. Li, S. Zhao, L. Zou, Spectral extrema of graphs with ﬁxed siz e: forbidden fan graph, friendship graph or theta graph, arXiv:2409.15918

arXiv

[7] [6]

Y. Li, L. Lu, Y. Peng, Spectral extremal graphs for the bowtie , Discrete Math. 346 (2023) 113680

work page 2023

[8] [7]

H. Lin, B. Ning, B. Wu, Eigenvalues and triangles in graphs, Comb. P robab. Comput. 30 (2021) 258–270

work page 2021