Article in volume
Authors:
Hajo Broersma
Department of Applied MathematicsFaculty EEMCSUniversity of TwenteP.O. Box 2177500 AE ENSCHEDETHE NETHERLANDS
email: h.j.broersma@utwente.nl
Title:
A note on minimum degree, bipartite holes, and Hamiltonian properties
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 717-726
Received: 2021-05-07 , Revised: 2022-07-08 , Accepted: 2022-07-08 , Available online: 2022-07-22 , https://doi.org/10.7151/dmgt.2464
Abstract:
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)=\emptyset$.
The bipartite-hole-number $\widetilde{\alpha}(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 $\delta(G)\geq \widetilde{\alpha}(G)-1$, and Hamilton-connected if
$\delta(G)\geq \widetilde{\alpha}(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
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer, New York, 2008).
- 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 - 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 - 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 - 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 - R. Gould, Advances on the Hamiltonian problem–-A survey, Graphs Combin. 19 (2003) 7–52.
https://doi.org/10.1007/s00373-002-0492-x - 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 - 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 - O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
https://doi.org/10.2307/2308928 - R.H. Shi, $2$-neighborhoods and hamiltonian conditions, J. Graph Theory 16 (1992) 267–271.
https://doi.org/10.1002/jgt.3190160310
Close