Geodesic
A note on minimum degree, bipartite holes, and Hamiltonian properties
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 717-726 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

We adopt the recently introduced concept of the bipartite-hole-number due to McDiarmid and Yolov, and extend their result on Hamiltonicity to other Hamiltonian properties of graphs with a large minimum degree in terms of this concept. An (s,t)-bipartite-hole in a graph G consists of two disjoint sets of vertices S and T with |S|=s and |T|=t such that E(S,T)=∅. The bipartite-hole-number α̃(G) is the maximum integer r such that G contains an (s,t)-bipartite-hole for every pair of nonnegative integers s and t with s+t=r. Our main results are that a graph G is traceable if δ(G)≥α̃(G)-1, and Hamilton-connected if δ(G)≥α̃(G)+1, both improving the analogues of Dirac's Theorem for traceable and Hamilton-connected graphs.
Keywords: Hamilton-connected graph, traceable graph, degree condition, bipartite-hole-number, minimum degree 
@article{DMGT_2024_44_2_a14,
     author = {Zhou, Qiannan and Broersma, Hajo and Wang, Ligong and Lu, Yong},
     title = {A note on minimum degree, bipartite holes, and {Hamiltonian} properties},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {717--726},
     year = {2024},
     volume = {44},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a14/}
}
TY  - JOUR
AU  - Zhou, Qiannan
AU  - Broersma, Hajo
AU  - Wang, Ligong
AU  - Lu, Yong
TI  - A note on minimum degree, bipartite holes, and Hamiltonian properties
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 717
EP  - 726
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a14/
LA  - en
ID  - DMGT_2024_44_2_a14
ER  - 
%0 Journal Article
%A Zhou, Qiannan
%A Broersma, Hajo
%A Wang, Ligong
%A Lu, Yong
%T A note on minimum degree, bipartite holes, and Hamiltonian properties
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 717-726
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a14/
%G en
%F DMGT_2024_44_2_a14
Zhou, Qiannan; Broersma, Hajo; Wang, Ligong; Lu, Yong. A note on minimum degree, bipartite holes, and Hamiltonian properties. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 717-726. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a14/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer, New York, 2008).

[2] V. Chvátal and P. Erdős, A note on Hamiltonian circuits, Discrete Math. 2 (1972) 111–113. https://doi.org/10.1016/0012-365X(72)90079-9

[3] 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

[4] G.-H. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984) 221–227. https://doi.org/10.1016/0095-8956(84)90054-6

[5] R.J. Faudree, R.J. Gould, M.S. Jacobson and R.H. Schelp, Neighborhood unions and hamiltonian properties in graphs, J. Combin. Theory Ser. B 47 (1989) 1–9. https://doi.org/10.1016/0095-8956(89)90060-9

[6] R. Gould, Advances on the Hamiltonian problem–-A survey, Graphs Combin. 19 (2003) 7–52. https://doi.org/10.1007/s00373-002-0492-x

[7] H. Li, Generalizations of Dirac's theorem in Hamiltonian graph theory–-A survey, Discrete Math. 313 (2013) 2034–2053. https://doi.org/10.1016/j.disc.2012.11.025

[8] C. McDiarmid and N. Yolov, Hamilton cycles, minimum degree, and bipartite holes, J. Graph Theory 86 (2017) 277–285. https://doi.org/10.1002/jgt.22114

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

[10] R.H. Shi, 2-neighborhoods and hamiltonian conditions, J. Graph Theory 16 (1992) 267–271. https://doi.org/10.1002/jgt.3190160310