REVIEW 2 major objections 2 minor 50 references
Krahn--Szeg\H{o} type inequalities and nodal domain methods on graphs
T0 review · 2 major / 2 minor · reviewed 2026-06-27 · grok-4.3
Pith's one-line read For connected graphs G of odd order n ≥ 5, |ρ₂| ⋅ ω ≤ m−2, with equality precisely when G is two complete graphs of orders (n+1)/2 and (n−1)/2 joined by an edge or a path.
desk verdict The paper settles the Aouchiche-Hansen conjecture via a new adjacency nodal domain theorem, but the Dirichlet-boundary reduction for the adjacency operator looks like it may not automatically deliver the claimed sharp equality cases. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The adjacency version of the nodal domain theorem obtained by viewing a connected graph as an internally disconnected graph equipped with Dirichlet boundary conditions.
What would settle it
A single connected graph of odd order n ≥ 5 that is not two cliques of sizes (n+1)/2 and (n−1)/2 joined by an edge or path, yet satisfies |ρ₂| ⋅ ω > m − 2.
Extended reading notes
Core claim
The core discovery is that the adjacency nodal domain theorem implies |ρ₂(G)| ⋅ ω(G) ≤ m(G) − 2 for connected graphs of odd order n ≥ 5, with equality if and only if G consists of two complete graphs of orders (n+1)/2 and (n−1)/2 joined by an edge or a path; for even n ≥ 2 the quantity |ρ₂| ⋅ ω − m is maximized exactly when G is obtained by adding one edge between two copies of K_{n/2}.
Load-bearing premise
That regarding a connected graph as an internally disconnected graph equipped with Dirichlet boundary conditions transfers the continuous nodal domain theorem and its extremal consequences to the discrete adjacency and Laplacian settings without loss of sharpness.
Editorial extensions
If this is right
- The bound implies several earlier results on adjacency eigenvalues of graphs.
- For trees with fixed numbers of interior vertices and boundary leaves, the structures minimizing the second Dirichlet eigenvalue are completely characterized.
- The method produces Krahn-Szegő type inequalities for trees.
- The Aouchiche-Hansen conjecture is settled with the stated equality cases for odd and even orders.
Reading between the lines
- If the Dirichlet perspective preserves sharpness for other operators, analogous bounds may apply to the normalized Laplacian or signed graphs.
- The extremal graphs suggest that near-maximizers for |ρ₂| ω tend to be nearly disconnected into two dense components.
- Numerical checks on small odd-order graphs outside the equality cases could confirm the gap size in the inequality.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper establishes a Krahn-Szegő-type inequality characterizing the trees minimizing the second Dirichlet eigenvalue for fixed interior vertices and boundary leaves. It proves an adjacency-matrix nodal domain theorem by regarding a connected graph as an internally disconnected graph equipped with Dirichlet boundary conditions at a cut. This is applied to obtain upper bounds on the second-largest adjacency eigenvalue ρ₂ and to resolve the Aouchiche-Hansen conjecture: for connected G of odd order n≥5, |ρ₂|⋅ω ≤ m−2 with equality precisely when G consists of two cliques of orders (n+1)/2 and (n−1)/2 joined by an edge or path; for even n the quantity |ρ₂|⋅ω−m is maximized exactly by the graph formed by adding one edge between two copies of K_{n/2}.
Significance. If the nodal-domain transfer is valid and the equality cases are sharp, the resolution of the 2010 Aouchiche-Hansen conjecture constitutes a substantial advance in extremal spectral graph theory. The perspective of imposing Dirichlet conditions on an internal cut supplies a systematic route for importing continuous nodal-domain arguments into the discrete adjacency and Laplacian settings and yields complete extremal characterizations for trees as well.
major comments (2)
- [nodal domain theorem for adjacency matrices] The resolution of the Aouchiche-Hansen conjecture (abstract, final paragraph) rests on the adjacency nodal domain theorem obtained by the internally-disconnected-with-Dirichlet-BC construction. Because the adjacency Rayleigh quotient is 2∑_{edges} u_i u_j rather than a difference form, imposing u=0 on the interface vertices changes the quadratic form; the manuscript must verify explicitly that this construction still forces the extremal graphs to be precisely the two-clique-plus-bridge constructions and excludes other nearly disconnected graphs that could satisfy the same nodal count while producing strictly larger |ρ₂|.
- [application to Aouchiche-Hansen conjecture] The equality cases stated for odd and even n (abstract) are load-bearing for the conjecture resolution. The paper should supply an independent verification—separate from the nodal-domain count—that no other graphs with the same ω and m attain the bound, for example by direct computation on small n or by showing that any deviation from the two-clique structure strictly decreases |ρ₂|.
minor comments (2)
- The abstract refers to “an adjacency version of the nodal domain theorem” without stating its precise hypotheses or conclusion; a self-contained statement should appear in the main text before its application.
- Notation for the second-largest adjacency eigenvalue is introduced as ρ₂(G) but the sign convention (whether ρ₂ denotes the second-largest or the one with smallest absolute value) should be fixed explicitly when the bound |ρ₂|⋅ω is stated.
Simulated Author's Rebuttal
We thank the referee for the detailed report and for highlighting the need for explicit verification of the adjacency nodal-domain construction and the equality cases. We address both major comments below and will incorporate the requested clarifications and checks in a revised version.
read point-by-point responses
-
Referee: The resolution of the Aouchiche-Hansen conjecture rests on the adjacency nodal domain theorem obtained by the internally-disconnected-with-Dirichlet-BC construction. Because the adjacency Rayleigh quotient is 2∑_{edges} u_i u_j rather than a difference form, imposing u=0 on the interface vertices changes the quadratic form; the manuscript must verify explicitly that this construction still forces the extremal graphs to be precisely the two-clique-plus-bridge constructions and excludes other nearly disconnected graphs that could satisfy the same nodal count while producing strictly larger |ρ₂|.
Authors: We agree that the change in quadratic form under Dirichlet conditions on the cut requires explicit justification for the adjacency case. The proof of the nodal-domain theorem (Section 3) already accounts for the adjacency bilinear form by showing that the Rayleigh quotient on the internally disconnected graph with zero boundary values is bounded above by the original ρ₂, with equality only when the eigenfunction is supported on the two components. In the revision we will add a dedicated paragraph immediately after the theorem statement that directly compares the quadratic forms: any graph with the same nodal count but additional edges crossing the cut would increase the cross terms in a way that forces |ρ₂| to decrease relative to the bridge case, thereby excluding other nearly disconnected candidates. This verification uses only the variational characterization already established in the paper. revision: yes
-
Referee: The equality cases stated for odd and even n are load-bearing for the conjecture resolution. The paper should supply an independent verification—separate from the nodal-domain count—that no other graphs with the same ω and m attain the bound, for example by direct computation on small n or by showing that any deviation from the two-clique structure strictly decreases |ρ₂|.
Authors: We will add an independent verification subsection. For odd n we include exhaustive enumeration for 5 ≤ n ≤ 9 (all connected graphs with given ω and m) confirming that only the stated two-clique-plus-edge/path graphs attain the bound; for larger n we supply a short monotonicity argument showing that replacing any non-clique block by a graph with the same order and fewer edges strictly lowers the contribution to ρ₂ while preserving ω. The even-n case receives an analogous small-n check (n=6,8) plus the observation that adding any edge inside one K_{n/2} block increases m without increasing |ρ₂| enough to compensate. These checks are independent of the nodal-domain count and will be placed in an appendix. revision: yes
Circularity Check
No circularity: new proofs and nodal-domain characterizations are self-contained
full rationale
The paper establishes its central results (Krahn-Szegő-type bounds on trees and the resolution of the Aouchiche-Hansen conjecture via an adjacency nodal-domain theorem) through explicitly stated new proofs that regard a connected graph as internally disconnected with Dirichlet conditions. No equation or claim reduces a derived quantity to a fitted parameter, a self-citation chain, or a definition that presupposes the target bound. The 2010 conjecture citation is external and non-overlapping; the nodal-domain transfer is presented as a fresh perspective whose validity is argued directly rather than imported. Consequently the derivation chain contains no load-bearing self-referential steps.
Assumptions & free parameters
assumptions (2)
- standard math Standard spectral properties of the adjacency and Laplacian matrices on finite graphs
- standard math Existence and basic properties of Dirichlet eigenvalues on graphs with boundary
Cite this review
Pith. "Pith review of Krahn--Szeg\H{o} type inequalities and nodal domain methods on graphs." pith.science (2026). https://pith.science/paper/DMZMBSIS
@misc{pith2026260611659,
author = {Pith},
title = {Pith review of: Krahn--Szeg\Ho type inequalities and nodal domain methods on graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/DMZMBSIS}},
note = {Machine review of arXiv:2606.11659}
}
abstract
We study discrete analogues of classical spectral geometric inequalities and extremal eigenvalue problems on graphs. The classical Krahn--Szeg\H{o} inequality states that, among bounded open subsets of $\mathbb{R}^n$ with fixed volume, the minimum of $\lambda_2(\Omega)$ is attained by the union of two congruent balls. Firstly, we establish a Krahn--Szeg\H{o} type inequality for trees. For trees with a fixed number of interior vertices and boundary leaves, we completely characterize the extremal structures that minimize the second Dirichlet eigenvalue. Secondly, we develop a nodal domain method for adjacency matrices. By proving an adjacency version of the nodal domain theorem for graphs, we obtain upper bounds for the second largest adjacency eigenvalue $\rho_2(G)$ of $G$ in given graph classes. These bounds imply some previous results. Finally, we settle the Aouchiche--Hansen conjecture (2010) on the second largest eigenvalue with given number of edges and clique number. We prove that for connected graphs $G$ of odd order $n \geq 5$, $|\rho_2| \cdot \omega \leq m-2$, with equality if and only if $G$ consists of two complete graphs of orders $\frac{n+1}{2}$ and $\frac{n-1}{2}$ joined by an edge or a path. For even $n \geq 2$, the quantity $|\rho_2| \cdot \omega - m$ is maximized exactly when $G$ is obtained by adding one edge between the two copies of $K_{n/2}$ by an edge. The core of the methods developed in this paper is to regard a connected graph as an internally disconnected graph with Dirichlet boundary condition. This perspective allows us to transfer nodal domain techniques from continuous spectral geometry to discrete settings and to obtain sharp extremal characterizations across diverse graph classes.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Aouchiche, P
M. Aouchiche, P. Hansen, A survey of automated conjectures in spectral graph theory, Linear Algebra Appl.432(2010) 2293–2322
2010
-
[2]
Bauer and G
F. Bauer and G. Lippner, Eigenvalue sum estimates for lattice subgraphs,Pure Appl. Math. Q.18(6)(2022) 2339–2353
2022
-
[3]
F. A. Berezin, Covariant and contravariant symbols of operators,Izv. Akad. Nauk SSSR Ser. Mat.36(1972), 1134–1167
1972
-
[4]
Bıyıko˘ glu and J
T. Bıyıko˘ glu and J. Leydold, Faber-Krahn type inequalities for trees,J. Combin. Theory Ser. B97(2)(2007) 159–174
2007
-
[5]
Brooks, M
G. Brooks, M. Gu, J. Hyatt, W. Linz and L. Lu, On the maximum second eigenvalue of outerplanar graphs,Discrete Math.348(5)(2025) Paper No. 114416, 27 pp
2025
-
[6]
A. E. Brouwer and W. H. Haemers,Spectra of Graphs, Springer, 2011
2011
-
[7]
Byrne, D
J. Byrne, D. N. Desai and M. Tait, A general theorem in spectral extremal graph theory, (2025),Trans. Amer. Math. Soc., to appear
2025
-
[8]
M. Cicalese, L. Kreutz, G. P. Leonardi and G. Morselli, The Quantitative Faber–Krahn Inequality for the Combinatorial Laplacian inZd. arXiv preprint arXiv:2504.21629 (2025)
Show all 50 references
-
[9]
Dautenhahn and L
E. Dautenhahn and L. Saloff-Coste, Faber-Krahn inequality and heat kernel estimates on glued graphs,Electron. J. Probab.31(2026), Paper No. 18, 37 pp
2026
-
[10]
E. B. Davies, G. M.L. Gladwell, J. Leydold and P. F. Stadler, Discrete nodal domain theorems,Linear Algebra Appl.336(2001), 51–60
2001
-
[11]
Favaron, M
O. Favaron, M. Mah´ eo and J.-F. Sacl´ e, Some eigenvalue properties in graphs (conjectures of Graffiti. II),Discrete Math.111(1993), no. 1-3, 197–220
1993
-
[12]
Filonov, M
N. Filonov, M. Levitin, I. Polterovich and D. Sher, P´ olya’s conjecture for Euclidean balls, Invent. Math.234(2023), no. 1, 129–169
2023
-
[13]
Filonov, M
N. Filonov, M. Levitin, I. Polterovich and D. Sher, P´ olya’s conjecture for Dirichlet eigen- values of annuli,J. Lond. Math. Soc. (2)113(2026), no. 2, Paper No. e70425, 37 pp
2026
-
[14]
R. L. Frank and S. Larson, Semiclassical inequalities for Dirichlet and Neumann Lapla- cians on convex domains,Comm. Pure Appl. Math.79(2026), no. 3, 762–822
2026
-
[15]
Freitas, A remark on P´ olya’s conjecture at low frequencies,Arch
P. Freitas, A remark on P´ olya’s conjecture at low frequencies,Arch. Math. (Basel)112 (2019), no. 3, 305–311
2019
-
[16]
Freitas and R
P. Freitas and R. Wang, P´ olya’s conjecture onS1 ×R, arXiv preprint arXiv:2506.04341 (2025)
2025
-
[17]
Friedman, Some geometric aspects of graphs and their eigenfunctions,Duke Math
J. Friedman, Some geometric aspects of graphs and their eigenfunctions,Duke Math. J. 69(3)(1993) 487–525. 38
1993
-
[18]
Z. Gan, R. Jiang and F. Lin, The improved Berezin-Li-Yau inequality and Kr¨ oger in- equality and consequences,Science China Mathematics, (2026), 1-20
2026
-
[19]
C. D. Godsil and G. F. Royle, Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer, New York, 2001
2001
-
[20]
J. Guo, C. Miao, W. Wang and G. Zhan, Improvement of P´ olya’s conjecture for balls and cylinders, arXiv preprint arXiv:2511.17050 (2025)
2025
-
[21]
He and C
W. He and C. Yu, Faber-Krahn inequalities for first Dirichlet eigenvalues of combinatorial p-Laplacian on graphs with boundary, arXiv preprint arXiv:2603.20814 (2026)
2026
-
[22]
He and C
W. He and C. Yu, An extension of Katsuda-Urakawa’s Faber-Krahn inequality, arXiv preprint arXiv:2603.27489 (2026)
2026
-
[23]
He and Z
X. He and Z. Wang, P´ olya’s conjecture for thin products, arXiv preprint arXiv:2402.12093 (2024)
2024
-
[24]
Henrot, Extremum problems for eigenvalues of elliptic operators,Frontiers in Math- ematics, Birkh¨ auser, Basel, 2006
A. Henrot, Extremum problems for eigenvalues of elliptic operators,Frontiers in Math- ematics, Birkh¨ auser, Basel, 2006
2006
-
[25]
Hong, A bound on the spectral radius of graphs,Linear Algebra Appl.108(1988), 135–139
Y. Hong, A bound on the spectral radius of graphs,Linear Algebra Appl.108(1988), 135–139
1988
-
[26]
Hong, Bounds of eigenvalues of a graph,Acta Math
Y. Hong, Bounds of eigenvalues of a graph,Acta Math. Appl. Sinica (English Ser.)4 (1988), no. 2, 165–168
1988
-
[27]
R. A. Horn and C. R. Johnson,Matrix Analysis, 2nd edition, Cambridge University Press, Cambridge, 2013
2013
-
[28]
Wang and X
H. Wang and X. M. Hou, Faber-Krahn type inequality for supertrees,Comput. Appl. Math.44(2025), no. 8, Paper No. 413, 16 pp
2025
-
[29]
Hua and R
B. Hua and R. Li, Eigenvalue estimates for the poly-Laplace operator on lattice sub- graphs,Calc. Var. Partial Differential Equations64(8)(2025) Paper No. 249, 25 pp
2025
-
[30]
Jiang and F
R. Jiang and F. Lin, P´ olya’s conjecture up toϵ-loss and quantitative estimates for the remainder of Weyl’s law, arXiv preprint arXiv:2507.04307 (2025)
2025 arXiv
-
[31]
S. R. Jog and S. L. Patil, Spectra ofkcoalescence of complete graphs,Asia Mathematika 5(2021) 113–118
2021
-
[32]
Kovaˇ r´ ık, S
H. Kovaˇ r´ ık, S. Vugalter and T. Weidl, Two-dimensional Berezin-Li-Yau inequalities with a correction term,Comm. Math. Phys.287(2009), no. 3, 959–981
2009
-
[33]
Leydold, A Faber-Krahn-type inequality for regular trees,Geom
J. Leydold, A Faber-Krahn-type inequality for regular trees,Geom. Funct. Anal.7(2) (1997) 364–378
1997
-
[34]
Leydold, The geometry of regular trees with the Faber-Krahn property,Discrete Math
J. Leydold, The geometry of regular trees with the Faber-Krahn property,Discrete Math. 245(1–3)(2002) 155–172
2002
-
[35]
Li and S.-T
P. Li and S.-T. Yau, On the Schr¨ odinger equation and the eigenvalue problem,Comm. Math. Phys.88(1983), no. 3, 309–318
1983
-
[36]
Li and K
Q. Li and K. Q. Feng, On the largest eigenvalues of graphs,Acta Math. Appl. Sinica2 (1979), 167–175
1979
-
[37]
H. Lin, L. Liu and Z. You, A Faber–Krahn inequality for trees, arXiv preprint arXiv:2601.01859 (2026)
2026
-
[38]
Lin and B
H. Lin and B. Ning, A complete solution to the Cvetkovi´ c–Rowlinson conjecture,J. Graph Theory97(3)(2021) 441–450
2021
-
[39]
Lov´ asz and J
L. Lov´ asz and J. Pelik´ an, On the eigenvalues of trees,Period. Math. Hungar.3(1973) 175–182
1973
-
[40]
Neumaier, The second largest eigenvalue of a tree,Linear Algebra Appl.46(1982), 9–25
A. Neumaier, The second largest eigenvalue of a tree,Linear Algebra Appl.46(1982), 9–25
1982
-
[41]
Rose, Gaussian upper heat kernel bounds and Faber-Krahn inequalities on graphs, arXiv preprint arXiv:2410.11715 (2024)
C. Rose, Gaussian upper heat kernel bounds and Faber-Krahn inequalities on graphs, arXiv preprint arXiv:2410.11715 (2024)
2024
-
[42]
Rowlinson, On the maximal index of graphs with a prescribed number of edges,Linear Algebra Appl.110(1988) 43–53
P. Rowlinson, On the maximal index of graphs with a prescribed number of edges,Linear Algebra Appl.110(1988) 43–53. 39
1988
-
[43]
Nikiforov, Some inequalities for the largest eigenvalue of a graph,Combinatorics, Probability and Computing11(2002),no
V. Nikiforov, Some inequalities for the largest eigenvalue of a graph,Combinatorics, Probability and Computing11(2002),no. 2, 179–189
2002
-
[44]
P´ olya, On the eigenvalues of vibrating membranes,Proc
G. P´ olya, On the eigenvalues of vibrating membranes,Proc. London Math. Soc. (3)11 (1961), 419–433
1961
-
[45]
D. L. Powers, Graph partitioning by eigenvectors,Linear Algebra Appl.101(1988), 121–133
1988
-
[46]
A. R. Pruss, Discrete convolution-rearrangement inequalities and the Faber-Krahn in- equality on regular trees,Duke Math. J.91(3)(1998) 463–514
1998
-
[47]
J. Y. Shao, On the largestkth eigenvalues of trees,Linear Algebra Appl.221(1995), 131–157
1995
-
[48]
Tait and J
M. Tait and J. Tobin, Three conjectures in extremal spectral graph theory,J. Combin. Theory Ser. B126(2017) 137–161
2017
-
[49]
L. You, M. Yang, W. So and W. Xi, On the spectrum of an equitable quotient matrix and its application,Linear Algebra Appl.577(2019) 21–40
2019
-
[50]
M. Zhai, H. Lin and B. Wang, Sharp upper bounds on the second largest eigenvalues of connected graphs,Linear Algebra Appl.437(2012), no. 1, 236–241. 40
2012
Reviewed June 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.