Cycles and paths through vertices whose degrees are at least the bipartite-hole-number
Cycles and paths through vertices whose degrees are at least the bipartite-hole-number
The bipartite-hole-number of a graph $G$, denoted by $\widetilde{\alpha}(G)$, is the minimum integer $k$ such that there exist positive integers $s$ and $t$ with $s + t = k + 1$, satisfying the property that for any two disjoint sets $A, B \subseteq V(G)$ with $|A| = s$ and $|B| = t$, there is at least one edge between $A$ and $B$. In 1992, Bollob\'as and Brightwell, and independently Shi, proved that every $2$-connected graph of order $n$ contains a cycle passing through all vertices whose degrees are at least $\frac{n}{2}$. Motivated by their result, we show that in any $2$-connected graph of order $n$, there exists a cycle containing all vertices whose degrees are at least $\widetilde{\alpha}(G)$. Moreover, we prove that for any pair of vertices in a connected graph $G$, if their degrees are at least $\widetilde{\alpha}(G) + 1$, then there exists a path joining them that contains all vertices whose degrees are at least $\widetilde{\alpha}(G) + 1$. The results extend two existing ones.
Chengli Li、Feng Liu、Yurui Tang
数学
Chengli Li,Feng Liu,Yurui Tang.Cycles and paths through vertices whose degrees are at least the bipartite-hole-number[EB/OL].(2025-06-11)[2025-07-19].https://arxiv.org/abs/2506.09750.点此复制
评论