图的多数控制数的下界(英文)

摘要

设G =(V ,E)是简单图 ,V表示G的顶点集 ,E表示G的边集 .对任何实值函数 f∶V→R和V的子集S ,令f(S) =∑u∈Sf(u) .设 f∶V→ {- 1,1}是G上的一个函数 .如果对于V的至少一半的顶点v ,f(N[v])≥ 1,则称f是G上的多数控制函数 .图G的多数控制数是γmaj(G) =min{f(V) | f是G上的一个多数控制函数 }.得到了这个参数的下界 ,推广了Henning的一些结果 .