树图的全控制数(英文)  

On the total domination number of trees

作　　者：侯新民[1] 

机构地区：[1]中国科学技术大学数学系,安徽合肥230026

出　　处：《中国科学技术大学学报》2006年第6期604-606,共3页JUSTC

基　　金：Supported by NNSF of China(10271114,10301031).

摘　　要：设G为n阶连通图,集合S称为图G的全控制集,如果V(G)的每个顶点都和S中某点相邻.图G的全控制数,记为tγ(G),是图G的全控制集的最小基数.证明了对阶数n≥3且T≠K1,n-1的树T,tγ(T)=min{2n3,n-l,n2+l-1},这里l表示树T中叶子的数目.For a given connected graph G of order n, a set S of vertices of G is a total dominating set, if every vertex of V（G） is adjacent to some vertex in S. The total domination number of G, denoted by γt, （G）, is the minimum cardinality of a total dominating set of G. We prove that, if T is a tree of order n〉1 and T ≠ K1,n-1,then γt（T）≤min{（2n）/3,n-l,[n/2]＋l-1},where l is the number of leaves of T.

关 键 词：全控制集 全控制数 

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