一类哈密顿图的控制数的上界  

Upper Bounds for the Domination Number of a Kind of Hamiltonian Graphs

作　　者：李同胜[1] 邢化明[1] 郭彦平[2] 史海燕[3] 

机构地区：[1]廊坊师范学院数学系,河北廊坊065000 [2]河北科技大学理学院,河北石家庄050018 [3]河北大学管理学院,河北保定071002

出　　处：《河北大学学报（自然科学版）》2006年第5期456-459,共4页Journal of Hebei University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(10371030);河北省教育厅自然科学基金资助项目(2005107)

摘　　要：设G=(V,E)是一个简单图,D是V的一个子集,如果集合V-D的任意点都与D中的点相邻,则称D为图G的一个控制集.图G的最小控制集中的点数称为G的控制数.本文对哈密顿图的控制数进行了研究,证明了命题:如果n阶图G是一个最小度为5的哈密顿图,则图G的控制数就不大于5n/14.Let G = （ V, E） be a simple graph. A subset D lohtain in V is a dominating set of G, if for any vertex u ∈V - D, there exists a vertex u E D such that uv ∈ E. The domination number of G equals the minimum cardinality of a domination set. In this paper, we will research the domination number of hamiltonian graphs and prove that for a hamiltonian graph G of order n with minimun degree at least five, the domination munber of is at most 5n/14

关 键 词：哈密顿图 控制数 上界 

分 类 号：O157.5[理学—数学]