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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

A counterexample to the Nordhaus-Gaddum product conjecture for the k-th Laplacian eigenvalue (Chen, Guo, Li and Wang, Conjecture 20)

Kerem Özdemir
Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
preprint

A counterexample to the Nordhaus-Gaddum product conjecture for the k-th Laplacian eigenvalue (Chen, Guo, Li and Wang, Conjecture 20)

Kerem Özdemir
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
A counterexample to the Nordhaus-Gaddum product conjecture for the k-th Laplacian eigenvalue (Chen, Guo, Li and Wang, Conjecture 20) — Kerem Özdemir · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS