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