图的符号全控制数

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)。

Abstract: 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).