3 papers
math.CO2026
The Distance Spectrum Does Not Determine Bipartiteness
Feifan Gong, Kehua Wang, Wei Wang
Over a decade ago, Koolen, Hayat, and Iqbal posed the problem of whether the distance spectrum determines bipartiteness within the class of connected graphs. In this paper, we reso…
math.CO2026
On the Spectral Determination of Complements of \(T\)-shape Trees
Feifan Gong, Kehua Wang, Wei Wang
A graph \(G\) is said to be \emph{determined by its spectrum} if every graph cospectral with \(G\) is isomorphic to \(G\). A \emph{T-shape tree} is defined as a tree containing exa…
cs.DS2026
An Exponent-Tight Conditional Lower Bound for Global Label Min-Cut
Yuanhao Wang, Wei Wang, Kehua Wang
Let and denote the numbers of vertices and labels, respectively, in an undirected edge-labeled graph. Previous work showed that, under the Exponential Time Hypothesis (ETH)…