摘要
设 G是 n个顶点的简单图 .运用 Reed引进的顶点不交的路覆盖 ,找出图 G的一个控制集并估算这个控制集的基数 ,结合估算结果 ,证明如果图 G的最小度至少是 5 ,则图 G有基数至多是 514 n的控制集 .
Let G be a simple graph of n vertices.In this paper,by using the so-called vertex disjoint path cover introduced by Reed,we prove that the domination number is at most 514n for the graphs of minimum degree at least five.
出处
《广西科学》
CAS
2004年第3期165-174,共10页
Guangxi Sciences
基金
广西青年科研基金 (桂青科 0 13 5 0 2 8)
国家自然科学基金( 10 1710 2 2 )资助项目
关键词
图
控制数
最小度
路覆盖
graph,domination number,minimum degree,path cover
