度为奇数的正则图的上负全控制数  

Upper Minus Total Domination of Regular Graphs

作　　者：吴建刚[1] 苗正科[2] 吕长虹[1] 

机构地区：[1]华东师范大学数学系,上海200241 [2]徐州师范大学数学学院,徐州221116

出　　处：《应用数学学报》2008年第5期861-870,共10页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(60673048);江苏省自然科学基金项目(BK2007030);江苏省普通高等学校“青蓝工程”中青年学术带头人;江苏省高校自然科学基金项目(07KJD110207)资助项目

摘　　要：f:V(G)→{-1,0,1}称为图G的负全控制函数,如果对任意点v∈V,均有f[v]≥1,其中f[v]=sum from v∈N(v)f(u).如果对每个点v∈V,不存在负全控制函数g:V(G)→{-1,0,1},g≠f,满足g(v)≤f(v),则称f是一个极小负全控制函数.图的上负全控制数Γ_t^-(G)=max{w(f)|f是G的极小负全控制函数},其中w(f)=sum from v∈V(G)f(v).本文研究正则图的上负全控制数,证明了,令G是一个n阶r-正则图.若r为奇数,则Γ_t^-(G)≤(r^2+1)/(r^2+2r-1)n.A function f：V（G）→{-1,0,1}defined on the vertices of a graph G is a minus total dominating function（MTDF）if the sum of its function values over any open neighborhood is at least one.An MTDF f is minimal if there does not exist an MTDF g：V（G）→{-1,0,1},f≠g,for which g（v）≤f（v）for every v∈V（G）.The weight of an MTDF is w（f）=∑ v∈V（G）f（v）.Thus,the upper minus total dominationΓt^-（G）is defined as follows：Γt^-（G）=max{w（f）｜f is minimal minus total dominating functon of G}.In this paper,we prove thatΓt^-（G）≤r^2＋1/r^2＋2r-1 n for r-regular graph G,when r is odd.

关 键 词：K-正则图 上负全控制数 控制数 

分 类 号：O157.5[理学—数学]