A Fan-type condition involving bipartite independence number for hamiltonicity in graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913888979648512 |
|---|---|
| author | Liu, Hongxi Yuan, Long-Tu Zhang, Xiaowen |
| author_facet | Liu, Hongxi Yuan, Long-Tu Zhang, Xiaowen |
| contents | The bipartite independence number of a graph $G$, denoted by $\widetildeα(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α(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α(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_02687 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Fan-type condition involving bipartite independence number for hamiltonicity in graphs Liu, Hongxi Yuan, Long-Tu Zhang, Xiaowen Combinatorics 05C45, 05C38 The bipartite independence number of a graph $G$, denoted by $\widetildeα(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α(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α(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. |
| title | A Fan-type condition involving bipartite independence number for hamiltonicity in graphs |
| topic | Combinatorics 05C45, 05C38 |
| url | https://arxiv.org/abs/2506.02687 |