Counterexamples to a conjecture of Zhou, Du and He on the two largest signless Laplacian eigenvalues

Zhou, Du and He (arXiv:2504.04389; Discrete Appl. Math. 384 (2026) 139-144, Conjecture 1) conjectured that among connected graphs with n vertices and cyclomatic number c (1 <= c <= n-2) the graph G(n-2-c, c) = K_1 v (K_{1,c} u (n-2-c)K_1) is the unique maximiser of q_1 + q_2, the sum of the two largest signless Laplacian eigenvalues. This note shows that the conjecture is false. For n = 5 and c = 2 the bowtie K_1 v 2K_2 has q_1 + q_2 = (13 + sqrt17)/2 = 8.5616, larger than 8.4893 for G(1, 2). For c = 3 and every n >= 5 the graph K_1 v (K_3 u (n-4)K_1) is signless-Laplacian cospectral with G(n-5, 3), so the maximiser is not unique; exhaustive search shows that both graphs attain the maximum for n <= 10, and that these are the only failures among connected graphs on at most 10 vertices. A standard-library Python script checks everything in exact rational arithmetic. Searches and verification were carried out with Claude (Anthropic) under the direction of Kerem Özdemir.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-27
DOI
https://doi.org/10.5281/zenodo.23685938
Primary Topic
Graph theory and applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Counterexamples to a conjecture of Zhou, Du and He on the two largest signless Laplacian eigenvalues

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

Counterexamples to a conjecture of Zhou, Du and He on the two largest signless Laplacian eigenvalues

Kerem Özdemir
preprint en

Abstract

Zhou, Du and He (arXiv:2504.04389; Discrete Appl. Math. 384 (2026) 139-144, Conjecture 1) conjectured that among connected graphs with n vertices and cyclomatic number c (1 <= c <= n-2) the graph G(n-2-c, c) = K_1 v (K_{1,c} u (n-2-c)K_1) is the unique maximiser of q_1 + q_2, the sum of the two largest signless Laplacian eigenvalues. This note shows that the conjecture is false. For n = 5 and c = 2 the bowtie K_1 v 2K_2 has q_1 + q_2 = (13 + sqrt17)/2 = 8.5616, larger than 8.4893 for G(1, 2). For c = 3 and every n >= 5 the graph K_1 v (K_3 u (n-4)K_1) is signless-Laplacian cospectral with G(n-5, 3), so the maximiser is not unique; exhaustive search shows that both graphs attain the maximum for n <= 10, and that these are the only failures among connected graphs on at most 10 vertices. A standard-library Python script checks everything in exact rational arithmetic. Searches and verification were carried out with Claude (Anthropic) under the direction of Kerem Özdemir.

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