摘要
将图的测地集与全控制集的概念结合,引入图的测地全控制集的定义,得到测地全控制数与测地数、测地控制数关系的一个基本结论:设图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.
出处
《中国计量学院学报》
2011年第3期291-294,共4页
Journal of China Jiliang University
基金
浙江省自然科学基金资助项目(No.Y6090472)
浙江省教育厅自然科学基金资助项目(No.Y200805913)
关键词
测地全控制集
测地数
弦图
NP-完全
geodetic total domination
geodetic number
chordal graph
NP-complete
