Spectral odd-cycle containment conjecture for the graph construction RkR_k

About 5 years old · traced to

Let kk be a positive integer, let GG be a non-bipartite graph of order n⩾2k+1n\geqslant 2k+1, and let Rk(H)R_k(H) denote the graph construction used in the source. Then

λ1(G)⩾λ1(Rk(K⌊(n−2k+1)/2⌋,⌈(n−2k+1)/2⌉)).\lambda_1(G)\geqslant \lambda_1\left(R_k\left(K_{\lfloor(n-2k+1)/2\rfloor,\lceil(n-2k+1)/2\rceil}\right)\right).

Spectral odd-cycle containment conjecture. Under this condition, GG contains at least one cycle from

{C3,C5,…,C2k+1},\{C_3,C_5,\ldots,C_{2k+1}\},

unless

G≅R(K⌊(n−2k+1)/2⌋,⌈(n−2k+1)/2⌉).G\cong R\left(K_{\lfloor(n-2k+1)/2\rfloor,\lceil(n-2k+1)/2\rceil}\right).

The conjecture extends the verified comparison in the source, which holds for 1⩽k⩽51\leqslant k\leqslant 5, to all positive integers kk. It is posed as an open problem in the supplied text.

References

Primary source

Shuchao Li, Wanting Sun and Yuantian Yu, “Adjacency eigenvalues of graphs without short odd cycles”, arXiv:2109.04599 (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.