Bondy's reverse degree-sum conjecture for long cycles

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=Cc=|C|, and let p\overline{p} be the order of a longest path in GCG-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\Greekmath01141\overline{p}\geq\Greekmath 0114 -1, then

c\Greekmath011B\Greekmath0114\Greekmath0114(\Greekmath01142).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.

Sources & referencesView supporting material

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.