On Some Versions of Conjectures of Bondy and Jung - Nikoghosyan, Zhora G. (Mathematical Problems of Computer Science, 2021)
Most known fundamental theorems in hamiltonian graph theory (due to Dirac, Ore, Nash-Williams, Bondy, Jung and so on) are related to the length of a longest cycle C in a graph G in terms of connectivity • and the length p of a longest path in G - C, for the special cases when k ≤ 3 and p ≤ 1 (if p = ¡1 then V (G ¡ C) = ; and C is called hamiltonian; and if p = 0 then V (G ¡ C) is an independent set of vertices and C is called dominating). Bondy (1980) and Jung (2001) conjectured a common generalization of these results in terms of degree sums including p and • as parameters. These conjectures still are open in the original form. In 2009, the minimum degree c¡versions (c - the length of a longest cycle in V (G - C)) of Conjectures of Bondy and Jung are shown to be true by the author (Discrete Math, v.309, 2009, 1925- 1930). In this paper, using another result of the author (Graphs and Combinatorics, v.29, 2013, 1531-1541), a number of analogous sharp results are presented including both p and c¡minimum degree versions of Conjectures of Bondy and Jung without connectivity conditions, inspiring a number of new strengthened and extended versions of conjectures of Bondy and Jung.