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

Some Upper Bounds for 2-domination Number of Graphs and a Graffiti.pc Conjecture

作　　者：柳忠伟 吴宝音都仍 LIU Zhongwei;WU Baoyindureng(College of Mathematics and System Sciences,Xinjiang University,Urumqi,Xinjiang,830046,P.R.China)

机构地区：[1]新疆大学数学与系统科学学院,乌鲁木齐新疆830046

出　　处：《数学进展》2021年第3期345-352,共8页Advances in Mathematics（China）

基　　金：Supported by NSFC(No.11571294);the Key Laboratory Project of Xinjiang(No.2018D04017)。

摘　　要：设G=(V(G),E(G))是一个图,k是一个正整数.称一个顶点子集S为G的kk-控制集,若V(G)\S中的每个顶点在S中至少有k个邻点,我们用rk (G)表示kk-控制集的最小阶数.令d_(1)≤d_(2)≤…≤d_(n)为图G的度序列.当n为偶数时,度序列中位数m(G)=d_(n/2+1),当n为奇数时,度序列中位数m(G)=d_(n+1/2).一个仍未解决的Graffiti.pc猜想说:对任一n个顶点的连通图G,r2(G)≤n-m(G)+1.首先我们证明了此猜想的一个弱形式:r2(G) ≤n-d_(1)+1.此外,通过拓展此猜想在二部图上的结果,我们证明了对最小度不小于2的无三角形图G,r2(G)≤n-Δ(G),其中Δ(G)为图G的最大度.众所周知,每一个其边数不少于顶点数的图都包含一个圈.我们将此结论推广到超图上.进而得到上述猜想对所有分裂图都成立.Let G=(V(G),E(G)) be a graph and k≥1 integer.A subset S■V(G) is called a k-dominating set of G if each vertex of V(G) \ S is adjacent to at least k vertices of S in G.The k-domination number of G,denoted by γk(G),is the cardinality of a minimum k-dominating set of G.Let d_(1)≤d_(2)≤…≤d_(n) be the degree sequence of G.The upper median m(G) of the degree sequence is defined as m(G)=d_(n+1/2) if n is odd and m(G)=d_(n/2+1) if n is even.An attractive conjecture of Graffiti.pc still remains open:for any connected graph G of order n,γ2(G)≤n-m(G)+ 1.First we show a weaker version of the conjecture:γ2(G)≤n-δ(G)+1.By extending a known result on bipartite graphs,we show that for any triangle-free graph G with δ(G)≥2,γ2(G)≤n-Δ(G),where Δ(G) is the maximum degree of G.It is a folklore that any graph G of size m and order n with m≥ n contains a cycle.By extending it to hypergraphs,we are able to verify the validity of the Graffiti.pc conjecture for all split graphs.

关 键 词：2-控制数 无三角形图 分裂图 超图 

分 类 号：O157.5[理学—数学]