Disproving a graph signing conjecture with a special 3-regular graph
A 3-regular counterexample to the Bilu--Linial signing conjecture
Discrete Mathematics
Summary
The Bilu-Linial signing conjecture suggested that for any regular graph, you could change the signs on its edges so that all eigenvalues of its adjacency matrix lie within a certain range. The authors found a specific kind of graph with each vertex connected to exactly three others, for which no such signing keeps the eigenvalues in that range. This means the conjecture is not true for all regular graphs. The proof is simple and relies on a small calculation and a recurrence method.
What this means in practice
- •For spectral graph algorithm designers: Know that certain edge signings cannot confine eigenvalues for 3-regular graphs, guiding algorithm choices in spectral methods.
- •For network modelers: Prevent assumptions of eigenvalue bounds in simulations of cubic networks with edge sign flips by using this counterexample.
A theory result. No direct application yet.
Authors
Zhiqiang Xu
Abstract
We construct a finite connected simple cubic graph $F$ such that every signing of its edges yields an adjacency matrix with an eigenvalue outside $[-2\sqrt2,2\sqrt2]$. This disproves the Bilu--Linial signing conjecture for general regular graphs. The proof is elementary, using a four-vertex calculation and a scalar recurrence.