Abstract
In this paper, we continue the study of domination and total domination in cubic graphs. It is known [Henning M. A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159-162] that every cubic graph has a dominating set and a total dominating set which are disjoint. In this paper we show that every connected cubic graph on n vertices has a total dominating set whose complement contains a dominating set such that the cardinality of the total dominating set is at most (n + 2)/2, and this bound is essentially best possible.
| Original language | English |
|---|---|
| Pages (from-to) | 699-708 |
| Number of pages | 10 |
| Journal | Central European Journal of Mathematics |
| Volume | 9 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - Jun 2011 |
Keywords
- Cubic graphs
- Hypergraph transversal
- Total domination
- Vertex partition
ASJC Scopus subject areas
- General Mathematics