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


Restrained domination in cubic graphs
Authors:Johannes H Hattingh  Ernst J Joubert
Institution:1.Department of Mathematics and Statistics,Georgia State University,Atlanta,USA;2.Department of Mathematics,University of Johannesburg,Auckland Park,South Africa
Abstract:Let G=(V,E) be a graph. A set SV is a restrained dominating set if every vertex in VS is adjacent to a vertex in S and to a vertex in VS. The restrained domination number of G, denoted γ r (G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show that if G is a cubic graph of order n, then gr(G) 3 \fracn4\gamma_{r}(G)\geq \frac{n}{4} , and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then gr(G) £ \frac5n11.\gamma _{r}(G)\leq \frac{5n}{11}. Lastly, we show that if G is a claw-free cubic graph, then γ r (G)=γ(G).
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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