2025/08/25 by Chen, Guantao, Lavrov, Mikhail, Ma, Yuying +2
#05C70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.18555
Let G be a simple graph. The k-th neighborhood of a vertex subset S ⊆ 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 ⊆ V(G) with |S| ≥ k and Λk(S) ≠ V(G). This parameter generalizes the classical binding number introduced by Woodall. Andersen showed that the condition β1(G) ≥ 1 does not guarantee the existence of a 1-factor in G, while Barát et al. proved that β2(G) ≥ 1 suffices for the existence of a 2-factor. In this paper, we extend this result to general k ≥ 2 by showing that any graph G with even k|V(G)| and βk(G) ≥ 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) ≥ 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) ≥ 1, the graph admits k disjoint matchings, each covering X.