Dehmer–Pickl–Shi–Yu conjecture comparing degree-power and Laplacian spectral distances

About 7 years old · traced to

Let TT and T′T' be two trees on nn vertices. Define the degree-power index

F2=∑v∈Vdeg⁡2(v).F_2=\sum_{v\in V}\deg^2(v).

Let dF2(T,T′)d_{F_2}(T,T') and dq1(T,T′)d_{q_1}(T,T') denote the graph distance measures induced by F2F_2 and by the largest Laplacian eigenvalue q1q_1, respectively.

Dehmer–Pickl–Shi–Yu conjecture. For every such pair of trees,

dF2(T,T′)≥dq1(T,T′).d_{F_2}(T,T') \geq d_{q_1}(T,T').

The conjecture is refuted by the computational search reported in the paper: counterexamples occur already for n=6n=6, and the number of counterexamples increases for the listed values of nn.

References

Primary source

Aleksandar Ilic and Matthias Dehmer, “On conjectures of network distance measures by using graph spectra”, arXiv:1912.08412 (2019).

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.