2025/11/01 by Ellingham, Mark, Huang, Yixuan, Wei, Bing · 1 citation
#05C38 #05C40 #Combinatorics (math.CO) #FOS: Mathematics #Primary: 05C45 #Secondary: 05C07
paper · doi:10.48550/arxiv.2511.00616
The \em bipartite-hole-number of a graph G, denoted as \widetildeα(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 ⊆ 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 δ(G) ≥ \widetildeα(G) is Hamiltonian. Later, Draganić, Munhá Correia and Sudakov proved that δ≥ \widetildeα(G) implies that G is pancyclic, unless G = K\frac n2, \frac n2. 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 σ2(G) ≥ 2 \widetildeα(G) - 1, and that a connected graph G contains a cycle through all vertices of degree at least \widetildeα(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 σ2(G) ≥ 2 \widetildeα(G) - 1, then it either contains a triangle or it is K\frac n2, \frac n2. Finally, we discuss the relationship between connectivity and the bipartite hole number.