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

李同胜; 邢化明; 郭彦平; 史海燕

doi:10.3969/j.issn.1000-1565.2006.05.003

河北大学学报(自然科学版) >

2006 , Vol. 26 >Issue 5: 456 - 459

DOI: https://doi.org/10.3969/j.issn.1000-1565.2006.05.003

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

李同胜 ,
邢化明 ,
郭彦平 ,
史海燕

展开

1.廊坊师范学院,数学系,河北,廊坊,065000； 2.河北科技大学,理学院,河北,石家庄,050018； 3.河北大学,管理学院,河北,保定,071002

网络出版日期: 2006-09-25

基金资助

国家自然科学基金，河北省教育厅自然科学基金

收起

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

LI Tong-sheng ,
XING Hua-ming ,
GUO Yan-ping ,
SHI Hai-yan

Expand

Online published: 2006-09-25

Fold

摘要

设G=(V,E)是一个简单图,D是V的一个子集,如果集合V-D的任意点都与D中的点相邻,则称D为图G的一个控制集.图G的最小控制集中的点数称为G的控制数.本文对哈密顿图的控制数进行了研究,证明了命题:如果n阶图G是一个最小度为5的哈密顿图,则图G的控制数就不大于5n/14.

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

本文引用格式

李同胜 , 邢化明 , 郭彦平 , 史海燕 . 一类哈密顿图的控制数的上界[J]. 河北大学学报(自然科学版), 2006 , 26(5) : 456 -459 . DOI: 10.3969/j.issn.1000-1565.2006.05.003

参考文献

[1] 邢化明, 王小英, XING Hua-ming, WANG Xiao-ying. 一类图的控制数的上界 [J]. 廊坊师范学院学报 2004.doi:10.3969/j.issn.1674-3210.2004.04.007
[2] GAREY M R, JOHNSON D S. Computers and intractability:a guide to the theory of NP-completeness [M]. San Franciso:W H Freeman 1979.
[3] ORE O. Theory of graphs [M]. Providence:Amer Math Soc Colloq Pub 1962.
[4] MCGUAIG W, SHEPHERD B. Domination in graphs with minimum degree two [J]. Journal of Graph Theory 1989, 13.
[5] REED B. PATHS, stars and the number three [J]. Comb Prob Comp 1996, 5.
[6] HAYNES T W, HEDETNIEMI S T, SLATER P J. Fundamentals of domination in graphs [M]. New Youk:Marcel Dekker 1998.
[7] CARO Y, RODITTY Y. A note on the k-domination number of a graph [J]. International Journal of Mathematics and Mathematical Sciences 1990, 13.
[8] CLARK W E, DUNNING L A. Tight upper bounds for the domination numbers of graphs with given order and minimum degree [J]. Electronic journal of Combinatorics 1997, 4.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

参考文献