图上Nordhaus-Gaddum型的符号全控制数的界(英文)  

Nordhaus-Gaddum Results for Signed Total Domination in Graphs

作　　者：史伟[1] 康丽英[1] 徐兰栓 

机构地区：[1]上海大学数学系,上海200444 [2]邢台广播电视大学,邢台050021

出　　处：《运筹学学报》2008年第2期67-72,共6页Operations Research Transactions

基　　金：the National Nature Science Foundation of China under grant 10571117;the Development Foundation of Shanghai Education Committee under grant 05AZ04

摘　　要：函数f:V(G)→{-1,1}称为图G的符号全控制函数,如果对每一个开邻域集上的点的函数值的和都大于等于1.符号全控制函数的权值是指图中所有点的函数值的求和.图的符号全控制数为图中所有符号全控制函数的最小权值.令G^-表示图G的补图.在该文中。我们研究符号全控制数的Nordhaus-Gaddum型不等式,给出了路与其补图的符号全控制数和的上界,以及图与其补图的符号全控制数和的下界.A function f ： V（G）→{-1,1} defined on the vertices of a graph G is a signed total dominating function （STDF） if the sum of its function values over any open neighborhood is at least one. The weight of a STDF is the sum of its function values over all vertices. Thesigned total domination number of G is the minimum weight of a STDF on G. Let G^- denote the complement of a graph G. In this paper we study Nordhaus-Gaddum type results for signed total domination number. An upper bound on γt^s（Pn）＋γt^s（P^-n） for a path Pn and a lower bound on γt^s（G）＋γt^s（G^-） are presented.

关 键 词：运筹学 符号全控制函数 Nordhaus-Gaddum型结果 补图 路 

分 类 号：O157.5[理学—数学] TS193.632[理学—基础数学]