Minimality conjecture for initial threshold graphs generated by RFI

About 5 years old · traced to

Let N>0N>0 and r≥2r\geq 2 be fixed, and let I=(0,N]I=(0,N]. Let TG(a1,…,ar)T_G(a_1,\ldots,a_r) be the initial threshold graph obtained from RFI(N,r)(N,r). Minimality conjecture. The graph GG is minimal: if G~⪯G\widetilde{G}\preceq G is also II-eigenvalue free, then G~=G\widetilde{G}=G. This conjecture asserts that no smaller threshold graph is (0,N](0,N]-eigenvalue free. The authors report exhaustive computational searches for several positive values of NN that found no smaller example, but the general claim remains open.

References

Primary source

Luiz Emilio Allem, Elismar R. Oliveira and Fernando Tura, “On I-eigenvalue free threshold graphs”, arXiv:2110.12107 (2021).

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.