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


Domination versus total domination in claw-free cubic graphs
Institution:Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, 2006 South Africa
Abstract:A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, every vertex in S is adjacent to some other vertex in S, then S is a total dominating set. The domination number γ(G) of G is the minimum cardinality of a dominating set in G, while the total domination number γt(G) of G is the minimum cardinality of total dominating set in G. A claw-free graph is a graph that does not contain K1,3 as an induced subgraph. Let G be a connected, claw-free, cubic graph of order n. We show that if we exclude two graphs, then γt(G)γ(G)127, and this bound is best possible. In order to prove this result, we prove that if we exclude four graphs, then γt(G)37n, and this bound is best possible. These bounds improve previously best known results due to Favaron and Henning (2008) 7], Southey and Henning (2010) 19].
Keywords:Domination  Total domination  Claw-free  Cubic
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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