|国家预印本平台
| 注册
首页|Strong binding numbers and factors

Strong binding numbers and factors

Strong binding numbers and factors

来源:Arxiv_logoArxiv
英文摘要

Let $G$ be a simple graph. The $k$-th neighborhood of a vertex subset $S \subseteq V(G)$, denoted $Λ^k(S)$, is the set of vertices that are adjacent to at least $k$ vertices in $S$. The $k$-th binding number $β^k(G)$ is defined as the minimum ratio $|Λ^k(S)|/|S|$ over all subsets $S \subseteq V(G)$ with $|S| \ge k$ and $Λ^k(S) \ne V(G)$. This parameter generalizes the classical binding number introduced by Woodall. Andersen showed that the condition $β^1(G) \ge 1$ does not guarantee the existence of a $1$-factor in $G$, while Barát et al. proved that $β^2(G) \ge 1$ suffices for the existence of a $2$-factor. In this paper, we extend this result to general $k \ge 2$ by showing that any graph $G$ with even $k|V(G)|$ and $β^k(G) \ge 1$ contains a $k$-factor. Moreover, if $G$ is additionally a split graph of even order, then it admits a $(k+1)$-factor. We also prove that any graph $G$ with $β^k(G) \ge 1$ contains at least $k-1$ disjoint perfect or near-perfect matchings. Finally, for any bipartite graph $G$ with bipartition $(X, Y)$, we introduce an analogue of the $k$-th binding number and show that, under the condition $β^k(G, X) \ge 1$, the graph admits $k$ disjoint matchings, each covering $X$.

Guantao Chen、Mikhail Lavrov、Yuying Ma、Jennifer Vandenbussche、Hein van der Holst

数学

Guantao Chen,Mikhail Lavrov,Yuying Ma,Jennifer Vandenbussche,Hein van der Holst.Strong binding numbers and factors[EB/OL].(2025-08-25)[2025-09-06].https://arxiv.org/abs/2508.18555.点此复制

评论