Geodesic
A note on minimum degree, bipartite holes, and Hamiltonian properties
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 717-726

Voir la notice de l'article provenant de la source Library of Science

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},
     publisher = {mathdoc},
     volume = {44},
     number = {2},
     year = {2024},
     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
PB  - mathdoc
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
%I mathdoc
%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/