局部度条件下的可去树

Connectivity Keeping Trees under a Local Degree Condition

摘要: 设G为图，ρG(v) = ν(G[NG(v)])，ν为匹配数。本文证明：对k ≥ 1、m ≥ 2，若k-连通图G对所有顶 点v满足dG(v) − ρG(v) ≥ 2k + 3m − 4，贝G含与任意给定mfl'树同构的可去子树，删去后仍k-连通， 这恢复了Chu等的无三角形界；当邻域匹配数不超过r时，给出充分条件δ(G) ≥ 2k + 3m + r − 4， 用Liu等的高连通三元组及顶点依赖匹配引理证明。

Abstract: For a graph G, let ρG(v) = ν(G[NG(v)]), where ν is the matching number. We prove that for k ≥ 1, m ≥ 2, if a k-connected graph G satisfies dG(v) − ρG(v) ≥ 2k + 3m − 4 for all vertices v, then G contains a connectivity keeping subtree isomorphic to any prescribed tree of order m, whose deletion leaves G k-connected. This recovers the triangle-free bound of Chu et al.; when all neighborhood matching numbers are at most r, we also obtain the sufficient condition δ(G) ≥ 2k + 3m + r − 4. The proof uses the highly connected triples of Liu et al. and a vertex-dependent matching lemma.