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

作者：柳忠伟; 吴宝音都仍

来源：数学进展, 2021, 50(03): 345-352.

• 2-控制数
• 无三角形图
• 分裂图
• 超图

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

• 出版日期2021