A counterexample to the Nordhaus-Gaddum product conjecture for the k-th Laplacian eigenvalue (Chen, Guo, Li and Wang, Conjecture 20)
Conjecture 20 of Q. Chen, J.-M. Guo, W.-J. Li and Z. Wang (Electron. J. Combin. 32(4) (2025) #P4.37) asserts that mu_k(G) mu_k(Gbar) <= n(n - k) for the k-th largest Laplacian eigenvalues of every graph G on n vertices and its complement, for every k <= 3n/4. The conjecture is false. The split graph of the Fano plane (points form a clique, lines an independent set, incidences as edges; n = 14, k = 6) gives mu_6(G) mu_6(Gbar) = 63 + 7 sqrt(57) > 112. More generally, the split graph of a symmetric 2-(v, kappa, lambda) design is a counterexample whenever v^2 - 4 v lambda + 4 kappa^2 > (v + 2 - kappa + lambda)^2; this holds for every finite projective plane and for every Hadamard 2-(4t-1, 2t-1, t-1) design with t >= 2 (t = 1 gives no counterexample). The note gives the statement as printed, both Laplacian characteristic polynomials, exact proofs, and the relation to Gibson (arXiv:2609.16049), which refutes only the equality clause at k = 3n/4. The archive contains the graphs (graph6 and adjacency lists) and a standard-library Python script that verifies the counterexamples with exact integer and rational arithmetic. Searches and verification were carried out with Claude (Anthropic) under the direction of Kerem Özdemir. Correction (2026-10-26): an earlier version of this description said "every Hadamard design"; the note's Corollary 4 requires t >= 2. Correction (2026-10-27): W. Jiang had disproved this conjecture before this record (Zenodo, doi:10.5281/zenodo.22238691, record of 6 September 2026), with a 16-vertex counterexample at k = 7 and violations for infinitely many n. This version does not cite that work; version 3 of this record does.
Authors
- Kerem Özdemir
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-26
- DOI
- https://doi.org/10.5281/zenodo.23669060
- Primary Topic
- Graph theory and applications
- Type
- preprint