摘要
设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.
基金
Supported by NNSF of China(10271114,10301031).
关键词
全控制集
全控制数
total dominating set
total domination number
