Graphs with disjoint dominating and paired-dominating sets |
| |
Authors: | Justin Southey Michael A Henning |
| |
Institution: | 1.Department of Mathematics,University of Johannesburg,Auckland Park,South Africa |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|