Edge degree conditions for dominating and spanning closed trails

Tian, Tao ; Broersma, Hajo  ; Xiong, Liming

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 363-381

Résumé

Edge degree conditions have been studied since the 1980s, mostly with regard to hamiltonicity of line graphs and the equivalent existence of dominating closed trails in their root graphs, as well as the stronger property of being supereulerian, i.e., admitting a spanning closed trail. For a graph G, let σ_2 (G)=min{d(u)+d(v)| uv∈ E(G)}. Chen et al. conjectured that a 3-edge-connected graph G with sufficientl large order n and σ_2 (G) gt; n/9-2 is either supereulerian or contractible to the Petersen graph. We show that the conjecture is true when σ_2 (G)≥ 2(⌊ n//15 ⌋-1). Furthermore, we show that for an essentially k-edge-connected graph G with sufficiently large order n, the following statements hold. (i) If k=2 and σ_2 (G)≥ 2(⌊ n//8 ⌋-1), then either L(G) is hamiltonian or G can be contracted to one of a set of six graphs which are not supereulerian; (ii) If k=3 and σ_2 (G)≥ 2(⌊ n//15 ⌋-1), then either L(G) is hamiltonian or G can be contracted to the Petersen graph.

Détail

Keywords: hamiltonicity, supereulerian, degree sum, line graph