Every 2-connected graph has a cycle through all vertices of degree at least its bipartite-hole-number, and high-degree pairs are joined by a path through all such vertices.
A Fan-type condition involving bipartite independence number for hamiltonicity in graphs
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
The bipartite independence number of a graph $G$, denoted by $\widetilde{\alpha}(G)$, is defined as the smallest integer $q$ for which there exist positive integers $s$ and $t$ with $s + t = q + 1$, such that for any two disjoint subsets $A, B \subseteq V(G)$ with $|A| = s$ and $|B| = t$, there exists an edge between $A$ and $B$. In this paper, we prove that for a 2-connected graph $G$ of order at least three, if $\max\{d_G(x), d_G(y)\} \ge \widetilde{\alpha}(G)$ for every pair of nonadjacent vertices $x, y$ at distance two, then $G$ is hamiltonian. Moreover, we prove that if $G$ is 3-connected and $\max\{d_G(x), d_G(y)\} \ge \widetilde{\alpha}(G)+1$ for every pair of nonadjacent vertices $x, y$ at distance two, then $G$ is hamiltonian-connected. Our results generalize the recent work by Li and Liu.
citation-role summary
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
REJECT 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Cycles and paths through vertices whose degrees are at least the bipartite-hole-number
Every 2-connected graph has a cycle through all vertices of degree at least its bipartite-hole-number, and high-degree pairs are joined by a path through all such vertices.