Geodesic
Edge degree conditions for dominating and spanning closed trails
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 363-381 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: hamiltonicity, supereulerian, degree sum, line graph 
@article{DMGT_2024_44_1_a18,
     author = {Tian, Tao and Broersma, Hajo and Xiong, Liming},
     title = {Edge degree conditions for dominating and spanning closed trails},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {363--381},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a18/}
}
TY  - JOUR
AU  - Tian, Tao
AU  - Broersma, Hajo
AU  - Xiong, Liming
TI  - Edge degree conditions for dominating and spanning closed trails
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 363
EP  - 381
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a18/
LA  - en
ID  - DMGT_2024_44_1_a18
ER  - 
%0 Journal Article
%A Tian, Tao
%A Broersma, Hajo
%A Xiong, Liming
%T Edge degree conditions for dominating and spanning closed trails
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 363-381
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a18/
%G en
%F DMGT_2024_44_1_a18
Tian, Tao; Broersma, Hajo; Xiong, Liming. Edge degree conditions for dominating and spanning closed trails. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 363-381. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a18/

[1] A. Benhocine, L. Clark, N. Köhler and H.J. Veldman, On circuits and pancyclic line graphs, J. Graph Theory 10 (1986) 411–425. https://doi.org/10.1002/jgt.3190100317

[2] J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).

[3] R.A. Brualdi and R.F. Shanny, Hamiltonian line graphs, J. Graph Theory 5 (1981) 307–314. https://doi.org/10.1002/jgt.3190050312

[4] P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44. https://doi.org/10.1002/jgt.3190120105

[5] P.A. Catlin, Z.-Y. Han and H.-J Lai, Graphs without spanning closed trails, Discrete Math. 160 (1996) 81–91. https://doi.org/10.1016/S0012-365X(95)00149-Q

[6] W.-G. Chen, Z.-H. Chen and M. Lu, Properties of Catlin's reduced graphs and supereulerian graphs, Bull. Inst. Combin. Appl. 75 (2015) 47–63.

[7] Z.-H. Chen, A degree condition for spanning eulerian subgraphs, J. Graph Theory 17 (1993) 5–21. https://doi.org/10.1002/jgt.3190170103

[8] Z.-H. Chen, Hamiltonicity and degrees of adjacent vertices in claw-free graphs, J. Graph Theory 86 (2017) 193–212. https://doi.org/10.1002/jgt.22120

[9] Z.-H. Chen and H.-J. Lai, Collapsible graphs and matchings, J. Graph Theory 17 (1993) 597–605. https://doi.org/10.1002/jgt.3190170506

[10] Z.-H. Chen and H.-J. Lai, Supereulerian graphs and the Petersen graph \uppercase\expandafter{\romannumeral2}}, Ars Combin. 48 (1998) 271–282.

[11] Z.-H. Chen, H.-J. Lai and M. Zhang, Spanning trails with variations of Chvátal–Erdős conditions, Discrete Math. 340 (2017) 243–251. https://doi.org/10.1016/j.disc.2016.08.002

[12] G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. (3) 2 (1952) 69–81. https://doi.org/10.1112/plms/s3-2.1.69

[13] R.J. Faudree, E. Flandrin and Z. Ryjáček, Claw-free graphs–-A survey, Discrete Math. 164 (1997) 87–147. https://doi.org/10.1016/S0012-365X(96)00045-3

[14] R.J. Gould, Recent advances on the Hamiltonian problem: survey \uppercase\expandafter{\romannumeral3}}, Graphs Combin. 30 (2014) 1–46. https://doi.org/10.1007/s00373-013-1377-x

[15] F. Harary and C.St.J.A. Nash-Williams, On Eulerian and Hamiltonian graphs and line graphs, Canad. Math. Bull. 8 (1965) 701–709. https://doi.org/10.4153/CMB-1965-051-3

[16] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55. https://doi.org/10.2307/2308928

[17] Y. Shao, Claw-free graphs and line graphs, Ph.D. Thesis (Morgantown, West Virginia University, 2005). https://doi.org/10.33915/etd.2251

[18] T. Tian and L. Xiong, Traceability on 2-connected line graphs, Appl. Math. Comput. 321 (2018) 463–471. https://doi.org/10.1016/j.amc.2017.10.043

[19] T. Tian and L. Xiong, 2-connected Hamiltonian claw-free graphs involving degree sum of adjacent vertices, Discuss. Math. Graph Theory 40 (2020) 85–106. https://doi.org/10.7151/dmgt.2125

[20] H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229–239. https://doi.org/10.1016/0012-365X(92)00063-W