Bondy's reverse degree-sum conjecture for long cycles

About 4 years old · traced to

Let GG be a graph with minimum degree \Greekmath010E\Greekmath 010E and connectivity \Greekmath0114\Greekmath 0114 , where 1≤\Greekmath0114≤\Greekmath010E1\leq\Greekmath 0114 \leq\Greekmath 010E . Let CC be a longest cycle in GG, let c=∣C∣c=|C|, and let p‾\overline{p} be the order of a longest path in G−CG-C. For a positive integer rr, let \Greekmath011Br\Greekmath 011B _r denote the minimum degree sum of an independent set of rr vertices.

Bondy's reverse degree-sum conjecture. If p‾≥\Greekmath0114−1\overline{p}\geq\Greekmath 0114 -1, then

c≥\Greekmath011B\Greekmath0114−\Greekmath0114(\Greekmath0114−2).c\geq\Greekmath 011B _\Greekmath 0114 -\Greekmath 0114 (\Greekmath 0114 -2).

This is the long-cycle analogue of Bondy's path version. The cases \Greekmath0114=1,2,3,4\Greekmath 0114 =1,2,3,4 have the cited partial results of Dirac, Bondy, Bermond, Linial, Fraisse, Yung, and Chiba, Tsugaki, and Yamashita; the general statement is not reported as resolved here.

References

Primary source

Zhora Nikoghosyan, “A Note on Large Cycles in Graphs Around Conjectures of Bondy and Jung”, arXiv:2211.16446 (2022).

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.