# A Note on Non-Dominating Set Partitions in Graphs

• Volume: 36, Issue: 4, page 1043-1050
• ISSN: 2083-5892

top

## Abstract

top
A set S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex of S and is a total dominating set if every vertex of G is adjacent to a vertex of S. The cardinality of a minimum dominating (total dominating) set of G is called the domination (total domination) number. A set that does not dominate (totally dominate) G is called a non-dominating (non-total dominating) set of G. A partition of the vertices of G into non-dominating (non-total dominating) sets is a non-dominating (non-total dominating) set partition. We show that the minimum number of sets in a non-dominating set partition of a graph G equals the total domination number of its complement G̅ and the minimum number of sets in a non-total dominating set partition of G equals the domination number of G̅ . This perspective yields new upper bounds on the domination and total domination numbers. We motivate the study of these concepts with a social network application.

## How to cite

top

Wyatt J. Desormeaux, Teresa W. Haynes, and Michael A. Henning. "A Note on Non-Dominating Set Partitions in Graphs." Discussiones Mathematicae Graph Theory 36.4 (2016): 1043-1050. <http://eudml.org/doc/287166>.

@article{WyattJ2016,
abstract = {A set S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex of S and is a total dominating set if every vertex of G is adjacent to a vertex of S. The cardinality of a minimum dominating (total dominating) set of G is called the domination (total domination) number. A set that does not dominate (totally dominate) G is called a non-dominating (non-total dominating) set of G. A partition of the vertices of G into non-dominating (non-total dominating) sets is a non-dominating (non-total dominating) set partition. We show that the minimum number of sets in a non-dominating set partition of a graph G equals the total domination number of its complement G̅ and the minimum number of sets in a non-total dominating set partition of G equals the domination number of G̅ . This perspective yields new upper bounds on the domination and total domination numbers. We motivate the study of these concepts with a social network application.},
author = {Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; total domination; non-dominating partition; nontotal dominating partition},
language = {eng},
number = {4},
pages = {1043-1050},
title = {A Note on Non-Dominating Set Partitions in Graphs},
url = {http://eudml.org/doc/287166},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Wyatt J. Desormeaux
AU - Teresa W. Haynes
AU - Michael A. Henning
TI - A Note on Non-Dominating Set Partitions in Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 4
SP - 1043
EP - 1050
AB - A set S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex of S and is a total dominating set if every vertex of G is adjacent to a vertex of S. The cardinality of a minimum dominating (total dominating) set of G is called the domination (total domination) number. A set that does not dominate (totally dominate) G is called a non-dominating (non-total dominating) set of G. A partition of the vertices of G into non-dominating (non-total dominating) sets is a non-dominating (non-total dominating) set partition. We show that the minimum number of sets in a non-dominating set partition of a graph G equals the total domination number of its complement G̅ and the minimum number of sets in a non-total dominating set partition of G equals the domination number of G̅ . This perspective yields new upper bounds on the domination and total domination numbers. We motivate the study of these concepts with a social network application.
LA - eng
KW - domination; total domination; non-dominating partition; nontotal dominating partition
UR - http://eudml.org/doc/287166
ER -

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.