Bipartite holes, degree sums and Hamilton cycles

The {\em bipartite-hole-number} of a graph $G$, denoted as $\tilde{\alpha }(G)$, is the minimum number $k$ such that there exist integers $a$ and $b$ with $a+b=k+1$ such that for any two disjoint sets $A,B\subseteq V(G)$, there is an edge between $A$ and $B$. McDiarmid and Yolov initiated research on bipartite holes by extending Dirac’s classical theorem on minimum degree and Hamiltonian cycles. They showed that a graph on at least three vertices with $\delta (G)\ge \tilde{\alpha }(G)$ is Hamiltonian. Later, Draganić, Munhá Correia and Sudakov proved that $\delta \ge \tilde{\alpha }(G)$ implies that $G$ is pancyclic, unless $G=K_{\frac{n}{2},\frac{n}{2}}$. This extended the result of McDiarmid and Yolov and generalized a theorem of Bondy on pancyclicity. In this paper, we show that a $2$-connected graph $G$ is Hamiltonian if ${\sigma }_2(G)\ge 2\tilde{\alpha }(G)-1$, and that a connected graph $G$ contains a cycle through all vertices of degree at least $\tilde{\alpha }(G)$. Both results extended McDiarmid and Yolov’s result. As a step toward proving pancyclicity, we show that if an $n$-vertex graph $G$ satisfies ${\sigma }_2(G)\ge 2\tilde{\alpha }(G)-1$, then it either contains a triangle or it is $K_{\frac{n}{2},\frac{n}{2}}$. Finally, we discuss the relationship between connectivity and the bipartite hole number.