A set ?$S$? of vertices in a graph ?$G$? is a total dominating set of ?$G$? if every vertex is adjacent to a vertex in ?$S$?. A fundamental problem in total domination theory in graphs is to determine which graphs have two disjoint total dominating sets. In this paper, we solve this problem by providing a constructive characterization of the graphs that have two disjoint total dominating sets. Our characterization gives an entirely new description of graphs with two disjoint total dominating sets and places them in another context, developing them from four base graphs and applies a sequence of operations from seventeen operations that are independent and necessary to produce all such graphs. We show that every graph with two disjoint total dominating sets can be constructed using this method.

Rights

URN

URN:NBN:SI:DOC-X3HHSNAG

COBISSID

18544217

Added

29.05.2020

Metadata

Citation

APA:

Henning, Michael A., Peterin, Iztok (2019). A characterization of graphs with disjoint total dominating sets. Ars mathematica contemporanea, volume 16, issue 2, str. 359-375. URN:NBN:SI:DOC-X3HHSNAG from http://www.dlib.si

MLA:

Henning, Michael A., Peterin, Iztok. "A characterization of graphs with disjoint total dominating sets." Ars mathematica contemporanea volume 16. issue 2 (2019) str. 359-375.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-X3HHSNAG>

Ars mathematica contemporanea
2008-
(Assembly record)