Conjecture on truncated generalized block Laplacian spectra

Let GG be a graph on nn vertices, with distinct degrees δ1>δ2>>δp\delta_1 > \delta_2 > \cdots > \delta_p. Set r=log2n+1r = \lceil\log_2 n\rceil + 1, partition V=i=1rViV = \bigsqcup_{i=1}^r V_i by taking ViV_i to be the vertices of degree δi\delta_i for i=1,,r1i=1,\ldots,r-1 and Vr=Vi=1r1ViV_r = V\setminus\bigsqcup_{i=1}^{r-1}V_i, and let eie_i be the characteristic vector of ViV_i and Ji,j=eiejJ_{i,j}=e_i e_j^\top. Define the truncated generalized block Laplacian spectrum using A=(AG,J1,1,J1,2,,Jr,r)\bm{A}=(A_G,J_{1,1},J_{1,2},\ldots,J_{r,r}). The truncated generalized block Laplacian conjecture. Almost all graphs are determined by their truncated generalized block Laplacian spectra. The claim proposes that this multivariate spectral invariant distinguishes almost every graph up to isomorphism; the source presents it as a conjecture for future research and gives only experimental evidence, so its resolution remains open.

Sources & referencesView supporting material

Primary source

Wei Wang and Da Zhao, “Graph isomorphism and multivariate graph spectrum”, arXiv:2412.20016 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.