王莹, 侯新民
令 γc(G) 为图 G 的 连通控制数. 如果γc(G)=k, 且对每一条边 e ∈ E(G), 有γc(G+e) ≤ k-1, 则称图 G 为 k-连通-控制-临界的,或简称为 k-c-临界的. 如果对每一对不同的点 u,v ∈ V(G),G-u-v 均含有完美匹配, 则图 G 称为双因子临界 的. 本文继续Ananchuen, Ananchuen 和 Plummer [Matching properties in connecteddomination critical graphs, Discrete Math., 2008]的工作, 证明了:(1) 设 G 是 3-连通 3-c-临界阶为 2n (n ≥ 4) 的图, 若图G 中任意一对不相邻的点 x,y, 满足 d(x)+d(y) ≥ 2n-2, 则图G 是双因子临界的. 这个结果推广了 Ananchuen, Ananchuen 和 Plummer上述工作中定理2.1. (2) 令 G 是 3-连通 3-c-临界且有 2n(n ≥ 4)个点的图, 若对 图 G 中任意两个距离为 2 的相异点 u 和v, 有 max{d(u),d(v)} ≥ n (Fan 条件), 则 G是双因子临界的. (3) 若图 G 是 3-连通 3-c-临界 且是K1,4-free 的偶阶图, 则 G 是双因子临界的. 这个结果改进了Ananchuen, Ananchuen 和 Plummer 上述工作中定理2.2.
