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 of G is the minimum cardinality of a dominating set in G, while the total domination number of G is the minimum cardinality of total dominating set in G. A claw-free graph is a graph that does not contain 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 , and this bound is best possible. In order to prove this result, we prove that if we exclude four graphs, then , 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 等数据库收录! |
|