完全多部图的符号罗马控制数

Signed Roman Domination of Multi-Partite Graph

设图G=(V,E)是一个简单无向图,若实值函数f:V→{-1,1,2}满足以下两个条件:(i)对于任意v∈V,均有∑_(u∈N[v])f(u)≥1成立;(ii)任意v∈V,若f(v)=-1,则存在一个与v相邻的顶点u∈V,满足f(u)=2,则称该函数为图G的符号罗马控制函数.定义图的符号罗马控制数为γSR(G)=min{f(V)f是图G的符号罗马控制函数}.通过对完全多部图中的顶点数进行分类,给出了当k≥3时,完全多部图K(n_1,…,n_i,…,n_k)的符号罗马控制数的准确值.

A signed Roman domination function, of a simple undirected graph G=（V,E）is a function f ：V→{-1,1,2} satisfying the conditions that （i）∑u∈N[v]f（u）≥1 for any v∈V, and（ii）every vertex v for which f（v）=-1 is adjacent to a vertex u for which f（u）=2. The signed roman domination number of G is γSR（G）=min{f（V） f is the signed roman domination of G}. In this paper, we compute the exact values of the signed roman domination numbers of complete multi-partite graph when k=3, through classification the vertex of G.