首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Domination number in graphs with minimum degree two
Authors:Er Fang Shan  Moo Young Sohn  Xu Dong Yuan  Michael A Henning
Institution:(1) Department of Mathematics, Shanghai University, Shanghai, 200444, P. R. China;(2) Department of Applied Mathematics, Changwon National University, 641-773 Changwon, Korea;(3) Department of Mathematics, Guangxi Normal University, Guilin, 541004, P. R. China;(4) School of Mathematical Sciences, University of KwaZulu-Natal, Pietermaritzburg, 3209, South Africa
Abstract:A set D of vertices of a graph G = (V,E) is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed’s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most (3n+|V 2|)/8, where V 2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number r k (G, γ) ≤ (3n+5k)/8 for all graphs of order n with minimum degree at least 3. This paper is dedicated to the memory of Professor Xudong Yuan.
Keywords:graph  dominating set  domination number  restricted domination number
本文献已被 维普 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号