图的测地全控制数  

On the geodetic total domination number of a graph

作　　者：赵敏[1] 

机构地区：[1]中国计量学院理学院,浙江杭州310018

出　　处：《中国计量学院学报》2011年第3期291-294,共4页Journal of China Jiliang University

基　　金：浙江省自然科学基金资助项目(No.Y6090472);浙江省教育厅自然科学基金资助项目(No.Y200805913)

摘　　要：将图的测地集与全控制集的概念结合,引入图的测地全控制集的定义,得到测地全控制数与测地数、测地控制数关系的一个基本结论:设图G为最小度δ≥2的任意图.如果图G的围长至少为6,则g(G)≤gγt(G)=tγ(G);给出路与圈上的测地全控制数的确定值,并证明弦图上的测地全控制集问题是NP-完全的.Combining the geodetic set and total dominating set,defined the geodetic total dominating set of a graph,proved a basic result of the relation between geodetic total domination number and geodetic number and geodetic domination number: Let G be a graph with minimum degree δ≥2.If G had girth at least 6,then g(G)≤γgt(G)=γt(G);presents the geodetic total domination number of a path and cycle,and proves Geodetic Total Dominating Set restricted to chordal graphs which is NP-complete.

关 键 词：测地全控制集 测地数 弦图 NP-完全 

分 类 号：TB9-55[一般工业技术—计量学]