图的符号全控制数

Signed Total Domination Number of Graphs

设图G=(V,E)为一个图,一个双值函数f:v→{-1,+1},若S?V,则记f(S)=∑V∈Sf(V)。如果对任意的顶点ν∈V,均有f(N(ν))≥1成立,则称f为图G的一个符号全控制函数。图G的符号全控制数定义为γst(G)=min{f(V)|f是图G的一个符号全控制函数}。本文首先给出一般图的符号全控制数的下界,然后用分类讨论和穷标法得到了两类图广义Petesen图P(n,k)和Double广义Petesen图DP(n,k)的符号全控制数的精确值,这里n≡0(mod3),k≠0(mod3)。

Let G=(V,E) be a graph and denotes f(S)=∑V∈Sf(V) for S?V. A function f:v→{-1,+1} is said to be a signed total domination function (STDF), if f(N(ν))≥1 for ν∈V. The signed total domination number is γst(G)=min{f(V)|f is an STDF of G}. In this paper, a lower bound of the signed total domination number are obtained and we determine a exact value of signed total domi-nation number of two classes graphs generalized Petesen graph P(n,k) and Double generalized Petesen graph DP(n,k) by exhaustived method and classified discussion, where n≡0(mod3),k≠0(mod3).