Abstract
A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired-dominating set of a graph is a dominating set such that the subgraph induced by the dominating set contains a perfect matching. In this paper, we show that no minimum degree is sufficient to guarantee the existence of a disjoint dominating set and a paired-dominating set. However, we prove that the vertex set of every cubic graph can be partitioned into a dominating set and a paired-dominating set.
| Original language | English |
|---|---|
| Pages (from-to) | 459-467 |
| Number of pages | 9 |
| Journal | Central European Journal of Mathematics |
| Volume | 8 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - Jun 2010 |
Keywords
- Cubic graph
- Domination
- Paired-domination
- Vertex partition
ASJC Scopus subject areas
- General Mathematics