Minimality conjecture for initial threshold graphs generated by RFI

Let N>0N>0 and r2r\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.

Sources & referencesView supporting material

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.