图的2-控制数的上界和一个Graffiti.pc猜想（英文）

设G=(V(G),E(G))是一个图,k是一个正整数.称一个顶点子集S为G的kk-控制集,若V(G)\S中的每个顶点在S中至少有k个邻点,我们用r_k (G)表示kk-控制集的最小阶数.令d₁≤d₂≤…≤d_n为图G的度序列.当n为偶数时,度序列中位数m(G)=d_n/2+1,当n为奇数时,度序列中位数m(G)=d_n+1/2.一个仍未解决的Graffiti.pc猜想说:对任一n个顶点的连通图G,r₂(G)≤n-m(G)+1.首先我们证明了此猜想的一个弱形式:r2(G) ≤n-d₁+1.此外,通过拓展此猜想在二部图上的结果,我们证明了对最小度不小于2的无三角形图G,r2(G)≤n-Δ(G),其中Δ(G)为图G的最大度.众所周知,每一个其边数不少于顶点数的图都包含一个圈.我们将此结论推广到超图上.进而得到上述猜想对所有分裂图都成立.