关于图中控制数γ_L,γ_t的关系

The relation on dominating number γ_L,γ_t in graph

G(V,E)是一个图且D V,如果N[D]=V,则称D为图G的控制集.进一步,对任一个控制集D1而言均有γ(〈D〉)≤γ(〈D1〉)成立,则称D为图G的小控制集,且小控制数γL(G)=min{|D|:D V且D是G的一个小控制集}.如果点集S V, X∈V均有N(X)∩S≠ 或∪N(x)=V,则称S为图G的全控制集,且全控制数γt(G)=min{|S|:S是G的一个全控制集}.x∈S本文证明:在树T中如果阶n≥2,则有γL(T)≤32γt(T)-1.

Let G(V,E) be a graph and DV. If N=V,then we call D a dominating set of G. Furthermore, for any other dominating set D1, if γ(<D>)≤γ(<D1>), then we call D a least dominating set of G, and the least dominating number γL(G)=min{|D|:DV and D is a least dominating set of G}. If SV,X∈V N(X)∩S≠ or ∪x∈SN(x)=V, then we call S a total dominating set of G. The total dominating number γt(G)=min{|S|:S is a total dominating set of G}. This paper proves: any Tree T of order n≥2,γL(T)≤32γt(T)-1.