图的全本征数的一个新上界

A NEW UPPER BOUND FOR THE TOTAL DOMINATION NUMBER OF A GRAPH

Cockayne,Dawes和Hedetniemi 证明了对于至少有三个点的连通图G,G的阶数P和G的全本征数γ_t(G)满足关系式γ_t(G)≤2p/3p。本文进一步研究了图G的全本征数。对于一个全本征数不低于3的连通图G,若G的最小度δ(G)不低于3且不超过P-4,则G的全本征数γ_t(G)不超过数x的整数部分,其中,x=2P/3-2δ(G)

A set of vertices in graph G is a total domination set, ifevery vertex in V is dominated by at least one vertex in D.The total domination number of G is the minimum number of vertices in a total dominating set of G. A upper bound for the total domination number of a graph was studied by, Cockayne, Dawes and Hedethiemi. This paper suggests another upper bound for the total domination number.