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

Lower Bounds on the Majority Domination Number of Graphs

设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的一些结果 .

Let G=(V,E) be a simple graph. For any real valued function f∶V→R and SV, let f(S)=∑ u∈S?f(u). A majority dominating function is a function f∶V→{-1,1} such that f(N)≥1 for at least half the vertices v∈V. Then majority domination number of a graph G is γ maj(G)=min{f(V)|f is a majority dominating function on G}. We obtain lower bounds on this parameter and generalize some results of Henning.