ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 16 (2019) 359-375 https://doi.org/10.26493/1855-3974.1525.7f3
(Also available at http://amc-journal.eu)
A characterization of graphs with disjoint total dominating sets*
*
Michael A. Henning *
Department of Pure and Applied Mathematics, University of Johannesburg, Auckland Park, 2006 South Africa
Iztok Peterin *
Faculty of Electrical Engineering and Computer Science, University ofMaribor, Koroska 46, 2000 Maribor, Slovenia
Received 8 November 2017, accepted 11 November 2018, published online 27 January 2019
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.
Keywords: Total domination number, disjoint total dominating sets. Math. Subj. Class.: 05C69
*The authors express their sincere thanks to the referees for their meticulous and thorough reading of the paper, and for their very helpful comments which improved the exposition and clarity of the revised version of the paper. In particular, we thank one of the reviewers for suggesting to us Claim 4.9 and Claim 4.10 which greatly simplified the original proof.
t Research supported in part by the South African National Research Foundation and the University of Johannesburg.
^This author is also affiliated with Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia. Research supported in part by the Slovenian Research Agency by the projects No. P1-0297 and No. J1-9109.
E-mail addresses: mahenning@uj.ac.za (Michael A. Henning), iztok.peterin@um.si (Iztok Peterin)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
360
Ars Math. Contemp. 16 (2019) 277-298
1 Introduction
A dominating set of a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S, where two vertices are neighbors if they are adjacent. A total dominating set of a graph G with no isolated vertex is a set S of vertices such that every vertex in G has a neighbor in S. Domination and its variations in graphs are now well studied. The literature on this subject has been surveyed and detailed in the two books by Haynes, Hedetniemi, and Slater [6, 7]. For a recent book on total domination in graphs we refer the reader to [13]. A survey of total domination in graphs can also be found in [9].
A classical result in domination theory, due to Ore [14] in 1962, is that every graph with no isolated vertex has two disjoint dominating sets. However, it is not the case that every graph with no isolated vertex can be partitioned into a dominating set and a total dominating set. Henning and Southey [11] showed that every connected graph with minimum degree at least two that is not a cycle on five vertices has a disjoint dominating set and a total dominating set. Further, in [12] they present a constructive characterization of connected graphs of order at least 4 that have a disjoint dominating set and a total dominating set. Disjoint dominating and total dominating sets in graphs are studied further, for example, in [10]. A characterization of graphs with disjoint dominating and paired-dominating sets is characterized in [15].
It remains, however, an outstanding problem to determine which graphs have two disjoint total dominating sets. Zelinka [16] in 1989 showed that no minimum degree condition in a graph is sufficient to guarantee that there exist two disjoint total dominating sets in the graph. Heggernes and Telle [8] showed that the decision problem to decide for a given graph G if it has two disjoint total dominating sets is NP-complete, even for bipartite graphs. Sufficient conditions for a graph to have two disjoint total dominating sets were obtained by Delgado, Desormeaux, and Haynes [4], but the authors in [4] were not able to characterize such graphs. Cubic graphs that have two disjoint total dominating sets were recently studied by Desormeaux, Henning and Haynes [5]. In particular, they show that cubic graphs that are 5-chordal or claw-free (we do not define these concepts here) can be partitioned into two total dominating sets.
The total domatic number tdom (G) of G is the maximum number of disjoint total dominating sets [3]. This can also be considered as a coloring of the vertices such that every vertex has a neighbor of every color (and has been called the coupon coloring problem [2]). Recent work on the total domatic number can be found, for example, in [1, 5]. The fundamental problem in total domination theory in graphs of determining which graphs have two disjoint total dominating sets can be phrased as follows: Determine which graphs G satisfy tdom(G) > 2. We call a graph a TDP-graph (standing for "total dominating partitionable graph") if its vertex set can be partitioned into two total dominating sets; that is, a graph G is a TDP-graph if and only if tdom(G) > 2.
In this paper, we provide a constructive characterization of the graphs that have two disjoint total dominating sets, or, equivalently, a characterization of the TDP-graphs. We describe a procedure to build TDP-graphs in terms of a 2-coloring of the vertices that indicate the role each vertex plays in the sets associated with the two disjoint total dominating sets. We show that the resulting family we construct, starting from four initial base graphs and applying one of seventeen operations to extend graphs in the family to larger graphs, is precisely the class of all TDP-graphs.
Our characterization provides a method for creating the TDP-graphs using a finite set of precise operations. The construction places the TDP-graphs in another context, devel-
M. A. Henning and I. Peterin: A characterization of graphs with disjoint total dominating sets 361
oping them from four base graphs and applying a sequence of operations from seventeen operations that are independent and necessary to produce a TDP-graph; that is, we show that this method produces precisely the family of TDP-graphs in that every graph generated by this method/algorithm is a TDP-graph and further every TDP-graph can be constructed in this way.
We remark that this procedure does not solve the decision problem to decide if a given graph has two disjoint total dominating sets in polynomial time. If one follows the steps in the proof of Section 4, one does indeed obtain an algorithm for this decision problem. However, this algorithm is far from polynomial time complexity. In particular, the first step of this algorithm is to discard some edges in order to obtain so-called sparse TDP-graph. Unfortunately, the proof does not provide those edges and this already spoils the time complexity.
1.1 Notation
For notation and graph theory terminology we generally follow [13]. All graphs in this paper are finite and simple, without loops or multiple edges. The order of a graph G is denoted by n(G) = |V(G)|, and the size of G by m(G) = |E(G)|. We denote the degree of a vertex v in the graph G by dG(v). The maximum (minimum) degree among the vertices of G is denoted by A(G) (¿(G), respectively). The open neighborhood of v is NG(v) = {u e V(G) | uv e E(G)}. For a set S C V(G), its open neighborhood is the set NG(S) = |Jves NG(v). For subsets X and Y of vertices of G, we denote the set of edges with one end in X and the other end in Y by [X, Y]. For a set S C V (G), the subgraph induced by S is denoted by G[S]. Further, the subgraph of G obtained from G by deleting all vertices in S and all edges incident with vertices in S is denoted by G - S; that is, G - S = G[V(G) \ S]. If S = {v}, we simply denote G - {v} by G - v.
The distance between two vertices u and v in G, denoted dG(u, v), is the minimum length of a (u, v)-path in G. By Wuv we denote the set of all vertices of G which are closer to u than to v; that is, Wuv = {w | dG(w, u) < dG(w, v)}. Symmetrically, Wvu is defined. A block of a graph G is a maximal connected subgraph of G which has no cut-vertex of its own. A block containing exactly one cut-vertex of G is called an end-block. It is well known that any two different blocks of a graph have at most one vertex in common, namely a cut-vertex. Furthermore, a connected graph with at least one cut-vertex has at least two end-blocks. Let X denote the set of cut-vertices of a connected graph G and let Y denote the set of its blocks. The block graph of G is a bipartite graph with partite sets X and Y in which a vertex x e X is adjacent to a vertex y e Y if x is a vertex of the block y. It is well-known that the block graph of any connected graph is a tree.
A walk is a finite, alternating sequence of vertices and edges in which each edge of the sequence joins the vertex that precedes it in the sequence to the vertex that follows it in the sequence. A non-backtracking walk is a walk with the additional constraint that no two consecutive edges on the walk are repeated.
Let u be a cut-vertex of a graph G. Let Hi and H2 be two vertex disjoint subgraphs of G - u that contain all the components of G - u, where each of Hi and H2 contain at least one component of G - u. We call Hi and H2 the associated subgraphs of G - u. For i € [2], we denote by Hu the subgraph of G induced by V(H) U {u}. Further, the vertex in Hu named u we rename u', and the vertex in Hu named u we rename u" in order to distinguish between u, u' and u''. We use the standard notation [k] = {1,..., k}.
362
Ars Math. Contemp. 16 (2019) 277-298
2 The graph family G
In this section, we construct a graph family G such that every graph in the family has two disjoint total dominating sets. First, we define a 2-coloring of a graph G as a partition S = (SR, SB) of V(G). The color of a vertex v, denoted color(v), is the letter X G {R, B} such that v g SX, where "R" and "B" here stand for red and blue, respectively. Thus, our 2-coloring of G is a coloring of the vertices of G, one color to each vertex, using the colors red and blue. We denote by X the letter X g {R, B} \ {X}, and we call X the color different from X. Thus, if X = R, then X = B while if X = B, then X = R. We denote by (G, S) a graph G with a given 2-coloring S. Our aim is to describe a procedure to build TDP-graphs in terms of 2-colorings. For i G [4], by a 2-colored Gj, we shall mean the graph Gj and its associated 2-coloring shown in Figure 1. Further, we call each 2-colored Gj a 2-colored base graph.
XX X__X X _ XX XX_ XX
XXX	XX X X XX	XX
(a) Gi	(b) G2	(c) G3	(d) G4
Figure 1: The four 2-colored base graphs Gi, G2, G3, G4.
Let G be the minimum family of 2-colored graphs that:
(i)	contains the four 2-colored base graphs; and
(ii)	is closed under the seventeen operations O1 through to O17 listed below, which extend a 2-colored graph (G', S') to a new 2-colored graph (G, S).
In Figures 2-7, the vertices of G' are colored black and the new vertices of G are colored white for illustrative purposes, even though the actual colors of the vertices are indicated by the letters X and X.
Operation O1: (G, S) is obtained from (G', S') by adding an edge between two nonadja-cent vertices of the same color. See the upper diagram of Figure 2.
Operation O2: (G, S) is obtained from (G', S') by adding an edge between two nonadja-cent vertices of different color. See the lower diagram of Figure 2.
1:
O2:
X*		Xf!
G'		1
X*		xi
		
X*		Xf
G'		1
X*		
Figure 2: The operations O1 and O2.
M. A. Henning and I. Peterin: A characterization of graphs with disjoint total dominating sets 363
Operation O3: If u and v are distinct vertices of different color from (G', S'), then (G, S) is obtained from (G', S') by adding a new vertex of any color adjacent to both u and v. See the left diagram in the upper part of Figure 3.
Operation O4: If u and v are distinct vertices of the same color from (G', S'), then (G, S) is obtained from (G', S') by adding adjacent vertices x and y and edges ux and vy with color(x) = color(y) = color(u). See the middle diagram in the upper part of Figure 3.
Operation O5: If u and v are distinct vertices of different color from (G', S'), then (G, S) is obtained from (G', S') by adding adjacent vertices x and y and edges ux and vy with color(x) = color(u) = color(y). See the right diagram in the upper part of Figure 3.
Operation O6: If u and v are distinct vertices of the same color from (G', S'), then (G, S) is obtained from (G', S') by adding a path xyz with color(y) = color(z) = color(x) = color(u) and adding edges ux and vz. See the left diagram in the lower part of Figure 3.
Operation O7: If u and v are distinct vertices of the same color from (G', S'), then (G, S) is obtained from (G', S') by adding a path xyzw and edges ux and vw with color(x) = color(w) = color(u) = color(y) = color(z). See the middle diagram in the lower part of Figure 3.
0a:
G'
X X«1
O4:
	X*)
G'	X*
?X
05
¿X
	x*1	—0
G'		
	X*-	-0
Oa:
G'
X*
X*
'X 'X
'X
X O
	X*]
G'	X»
XX
—O-Q
X X
»8
G'
X*
X*
XX
—O-Q
XX
Figure 3: The operations O3 - O8.
Operation O8: If u and v are distinct vertices of different color from (G', S'), then (G, S) is obtained from (G', S') by adding a path xyzw and edges ux and vw with color(x) = color(y) = color(v) = color(z) = color(w). See the right diagram in the lower part of Figure 3.
Operation O9: If u and v are adjacent vertices of different color from (G', S'), then (G, S) is obtained from (G', S') by subdividing uv with four consecutive vertices x, y, z, w where x is adjacent to u and color(u) = color(z) = color(w) = color(x) = color(y). See the upper diagram of Figure 4.
Operation Oi0: If u and v are adjacent vertices of the same color from (G', S'), then (G, S) is obtained from (G', S') by subdividing uv with four consecutive vertices x, y, z, w where x is adjacent to u and color(u) = color(x) = color(w) = color(y) = color(z). See the lower diagram of Figure 4.
Operation O11: If v is a vertex from (G', S'), then (G, S) is obtained from (G', S') by adding an edge xy together with the edges vx and vy where color(x) = color(y) = color(v). See the left diagram of Figure 5.
Operation O12: If v is a vertex from (G', S'), then (G, S) is obtained from (G', S') by
364
Ars Math. Contemp. 16 (2019) 277-298
09:
O
10:


Figure 4: The operations O9 and O10.
adding a path xyz together with the edges vx and vz where color(x) = color(y) = color(z) = color(v). See the middle diagram of Figure 5.
Operation O13: If v is a vertex from (G', S'), then (G, S) is obtained from (G', S') by adding a path xyzw together with the edges vx and vw where color(x) = color(w) = color(v) = color(y) = color(z). See the right diagram of Figure 5.
Figure 5: The operations O11, O12 and O13.
Operation O14: If v is a vertex from (G',S'), then (G, S) is obtained from (G',S') by adding a 3-cycle, xyzx, together with the edge vx where color(x) = color(v) = color(y) = color(z). See the left diagram of Figure 6.
Operation O15: If v is a vertex from (G', S') of any color, then (G, S) is obtained from (G', S') by adding a 4-cycle, xyzwx, together with the edge vx where color(x) = color(y) = color(z) = color(w). See the middle diagram of Figure 6, where the notation X/X means that the vertex can have any color.
Operation O16: If v is a vertex from (G', S'), then (G, S) is obtained from (G', S') by adding a 5-cycle, xyzwtx, together with the edge vx where color(x) = color(y) = color(t) = color(z) = color(w) = color(v). See the right diagram of Figure 6.
Figure 6: The operations O14, O15 and O16. Operation O17: If u is a cut-vertex from (G', S') with associated subgraphs Hf and
M. A. Henning and I. Peterin: A characterization of graphs with disjoint total dominating sets 365
and in (u') there exists a vertex of the same color as u and in NH% (u'') there exists a vertex of different color as u, then (G, S) is obtained from Hf and Hf by adding a new vertex v and the edges u'v and vu''. The color of all vertices from Hf remains the same as in G', color(v) = color(u") = color(u') = color(u) and the color of all vertices from Hf is exchanged with respect to their color in G'. See the diagram of Figure 7, where the notation A means that the color of all vertices from the set A in (G', S') is changed in (G, S).
Oir:

		
	v -0- X	X A X
Figure 7: The operation O17.
We remark that, by definition, all operations O3 to O17 produce new vertices. Further, exactly one new vertex created in each of the operations O14 to O16 has degree 3, and all other new vertices created using operations O3 to O17 have degree 2 in G. In operations O11 to O13, if the selected vertex v from (G', S') is a cut-vertex of G' it is also a cutvertex in G, while if v is not a cut-vertex of G' it becomes a cut-vertex in G. Moreover all operations from O14 to O17 produce new cut vertices. In this sense all operations, except O1 and O2, can be viewed as base operations which build the sparse skeleton of TDP-graphs, while O1 and O2 fill this skeleton with additional edges. This is also the main idea of the proof. First to discard all edges which are there by one of the operations O1 and O2, and then study the resulting vertices of degree two.
Lemma 2.1. If (G, S) G G for some 2-coloring S = (SR, SB), then G is a TDP-graph. Further, S = (SR, SB) is a partition of V(G) into two total dominating sets of G.
Proof. We proceed by induction on the number, k > 0, of operations O1 through O17 used to construct a 2-colored graph (G, S) G G .If k = 0, then (G, S) is one of the four 2-colored base graphs illustrated in Figure 1, and one can readily observe that G is a TDP-graph and S = (SR, SB) is a partition of V(G) into two total dominating sets of G. This establishes the base case. Let k > 1 and suppose that every 2-colored graph (G', S') g G that can be constructed using fewer than k operations satisfies the desired result.
Let (G, S) g G be a 2-colored graph that can be built from one of the 2-colored base graphs by a sequence of k operations O1 -O17. Let Oj be the last operation of that sequence where j G [17], and let (G', S') be the graph obtained from the same 2-colored base graph with the same sequence as that used to construct (G, S) but without applying the last operation Oj. Thus, (G', S') G G can be constructed using fewer than k operations.
By the induction hypothesis, the graph G' is a TDP-graph and S' = (Sa, Sb) is a partition of V (G') into two total dominating sets of G'. If j G [2], then S = S' and G is a TDP-graph since no new vertices were added. For 3 < j < 17 it is a simple exercise to check from the color of the new vertices added to (G', S') when forming (G, S) that the operation Oj yields two disjoint total domination sets, namely SR and SB. Thus, G is a TDP-graph, and S = (SR, SB) is a partition of V(G) into two total dominating sets of G.	□
366
Ars Math. Contemp. 16 (2019) 277-298
3	Main result
Our main result is to provide a constructive characterization of the graphs that have two disjoint total dominating sets, or, equivalently, a characterization of the TDP-graphs.
We prove that the class of all TDP-graphs is precisely the family G constructed in Section 2. A proof of Theorem 3.1 is given in Section 4.
Theorem 3.1. A graph G is a TDP-graph if and only if every component of (G, S) is in G for some 2-coloring S. Further, if (G, S) G G, then S = (SR, SB) is a partition of V(G) into two total dominating sets of G.
4	Proof of Theorem 3.1
The sufficiency follows from Lemma 2.1. To prove the necessity, let G be a TDP-graph and let S = (SR, SB) be a partition of V(G) into two total dominating sets of G. We show that (G, S) G G by induction on m = |E(G) |. Since G is a TDP-graph, we note that ¿(G) > 2, G has order n > 4, and m > 4. If m = 4, then necessarily G = C4, and (G, S) is the 2-colored base graph Gi, and so (G, S) g G. This establishes the base case. Let m > 5 and assume that every TDP-graph G' of size less than m where S' = (Sr, S'B) is a partition of V(G') into two total dominating sets satisfies (G', S') G G.
Let G be a TDP-graph of order n and size m, and let S = (SR, SB) be a partition of V (G) into two total dominating sets of G. If G is disconnected, we apply the inductive hypothesis to each component of G to produce the desired result. Hence, we may assume that G is connected.
Our general strategy in what follows is to reduce the graph G to a TDP-graph G' of size less than m, apply the inductive hypothesis to G' to show that (G', S') G G, and then reconstruct the graph (G, S) from (G', S') by applying one of the operations Ox, x G [17], to show that (G, S) G G. We state this formally, since we will frequently use the following statement.
Statement 4.1. If G' is a TDP-graph of size less than m, where S' = (Sr, Sb) is a partition of V(G') into two total dominating sets, and (G, S) can be constructed from (G', S') by applying one of the operations Ox, where x G [17], then (G, S) G G.
We define three graphs GR, GB and GRB associated with the graph G and the partition
5	= (SR, SB). Let Gr and GB be the subgraphs of G induced by the sets SR and SB, respectively, and so GR = G[SR] and GB = G[SB]. Let GRB be the (spanning) subgraph
of G with V(Grb) = V(G) and E(Grb) = E(G) \ (E(Gr) U E(Gb)).
Claim 4.2. If some component of GR, GB or GRB is not a star, then (G, S) G G.
Proof. Suppose that there exists a component, C, of GR, GB or GRB which is not a star. If C contains a cycle v1... vkv1, k > 3, then G can be obtained from G' = G — v1v2 by either applying operation Oi in the case when C is a component of Gr or Gb or by applying operation O2 in the case when C is a component of GRB. If C contains no cycle, then C is a tree different from a star. Therefore, there exists a path u1u2u3u4 in C and G can be obtained from G' = G — u2u3 by either applying operation O1 in the case when C is a component of GR or GB or by applying operation O2 in the case when C is a component of Grb. In all cases, since S = (SR, SB) is apartition of V(G) into two total dominating sets of G, the same partition S' = S = (SR, SB) is a partition of V(G') into two total
M. A. Henning and I. Peterin: A characterization of graphs with disjoint total dominating sets 367
dominating sets of G'. By the inductive hypothesis, (G', S') G G. We can obtain G from the same 2-colored base graph as G' and the same sequence of operations from O - Oi7 used to construct (G', S') by adding at the end of this sequence the operation O or O2. Hence (G, S) G G.	□
By Claim 4.2, we may assume that every component of GR, GB or GRB is a star, for otherwise the desired result follows. We call the resulting graph G a sparse TDP-graph with associated partition S = (SR, SB).
We now partition the sets SR and SB in two different ways depending on the role that the vertices in SR and SB, respectively, play in the graphs GR, GB and GRB. First, let SR = Ri U R2 U R3 and SB = Bi U B2 U B3 where
Ri = {v G Sr | (v) > 2}
R2 = {v G Sr \ Ri | Ng(v) n Ri = 0}
R3 = Sr \ (Ri U R2)
and
Bi = {v G Sb | dgb (v) > 2}
B2 = {v G Sb \ Bi | Ng(v) n Bi = 0}
B3 = Sb \ (Bi U B2).
Next, we define a partition of V(G) = V(GRB) as the union of the two partitions
SR = RiB U R2B U R3B and SB = RBi U RB2 U RB3 where
RiB = {v G Sr | ¿grb (v) > 2}
R2B = {v G SR \ RiB | v has a neighbor in GRB that belongs to RBi} R3B = Sr \ (RiB U R2B)
and
RBi = {v G Sb | dgrb (v) > 2}
RB2 = {v G SB \ RBi | v has a neighbor in GRB that belongs to RiB} RB3 = Sb \ (RBi U RB2).
We note that every vertex in R3 has degree 1 in GR, and every vertex in R3B has degree 1 in GRB. Analogously, every vertex in B3 and RB3 has degree 1 in GB and GRB, respectively. In particular, vertices from R3 n R3B and from B3 n RB3 have degree 2 in G. Further, the neighbor of a vertex from R3 in GR belongs to R3, and, analogously, the neighbor of a vertex from B3 in GB belongs to B3. We proceed further with the following series of structural properties of the graph G.
Claim 4.3. ¿(G) = 2.
Proof. Recall that G is a sparse TDP-graph with associated partition S = (SR, SB). Thus, SR and SB are disjoint total dominating sets of G which form a partition of V(G). Every vertex v g V(G) has at least one neighbor in SR and at least one neighbor in SB. Hence, ¿(G) > 2. Suppose, to the contrary, that ¿(G) > 2.
368
Ars Math. Contemp. 16 (2019) 277-298
Suppose that RiB = 0 and let v e RiB. Let vi,..., vk, where k > 2, be the neighbors of v in GRB . By Claim 4.2 and the definition of the set RB2, we note that for each i e [k], vi e RB2 and the vertex v is the only neighbor of vi that belongs to the set SR. Further, since da(vi) > 2, the vertex vj has at least two neighbors in SB. By Claim 4.2, every component of the graph GB is a star, implying that no two neighbors of v are adjacent or have a common neighbor in GB. Further, every neighbor of vi in G different from v belongs to the set B2, and has the vertex vi as its only neighbor in GB. Thus, the set B2 contains at least 2k vertices at distance 2 from v in G.
For i e [k], let wi denote an arbitrary neighbor of vi in GB, and so wi e B2. Since dG (wi) > 2 and wi has only one neighbor in SB, namely the vertex vi, we note that wi e RBi and therefore wi has at least two neighbors in R2B. By Claim 4.2 and the definition of the set R2B, we note that every neighbor of wi different from vi belongs to the set R2B. Further, each such neighbor of wi has exactly one neighbor that belongs to the set SB, namely the vertex wi, and therefore has at least two neighbors in SR by the minimum degree condition. By Claim 4.2, every component of the graph GR is a star, and therefore two distinct vertices of degree at least 2 in GR belong to different components of GR. This implies that this subset R2B of vertices in SR contains at least 4k vertices.
By the minimum degree condition, these vertices in R2B also belong to Ri and each of them has at least two neighbors in R2. Further, analogously as before, no two such vertices are the same, implying that this subset of R2 contains at least 8k - 1 vertices distinct from v, all of which belong to the set RiB, noting that one of these vertices may possibly be the vertex v. By repeating this process for all these vertices we see that we have an infinite process with infinite growth, which is not possible in a finite graph G. Therefore, the set RiB = 0. Analogously, the set RBi = 0. Therefore, R2B and RB2 are also empty.
We now consider a vertex v e R3B. By Claim 4.2, every component of the graph GRB is a star, implying that the vertex v has exactly one neighbor in Sb and, by the minimum degree condition, at least two neighbors in SR. Thus, v e Ri and each neighbor of v in SR belong to R2. Further, by Claim 4.2, each such neighbor of v in R2 has degree 1 in GR and, therefore, by the minimum degree condition, has at least two neighbors in SB. Thus, every neighbor of v in R2 belongs to the set RiB, contradicting our earlier observation that the set RiB is an empty set. This completes the proof of Claim 4.3.	□
By Claim 4.3, every sparse TDP-graph has minimum degree 2. In particular, ¿(G) = 2. Let D = {v e V(G) | dG(v)=2}.
Claim 4.4. If a vertex in D is a cut-vertex of G, then (G, S) e G.
Proof. Suppose that a vertex in D is a cut-vertex of G. Suppose firstly that D contains two adjacent vertices, x and y, that are both cut-vertices of G, and let e = xy. Let Cx and Cy be the components of G — e which contain x and y, respectively. Further, let xX be the neighbor of x in Cx and let y' be the neighbor of y in Cy. We have two possibilities with respect to the color of the vertices x, x', y, y'. Either color(x') = color(x) = color(y) = color(y') or color(x') = color(y') = color(x) = color(y). In both cases, let G' be the graph obtained from G — {x, y} by adding the edge x'y', and changing the color of all vertices in V(Cy) \ {y} while retaining the color of all vertices in V(Cx) \ {x}. Let S' = (Sr, Sb) be the resulting partition of V(G'). We note that G' is a TDP-graph, where S' = (Sr, S'B) is a partition of V(G') into two total dominating sets and that x' and y' are cut vertices of G'. If x and x' have the same color in G, then we use Statement 4.1 with the operation Oi7
M. A. Henning and I. Peterin: A characterization of graphs with disjoint total dominating sets 369
and the cut vertex y' to show that (G, S) G G, while if x and x' have different color in G, we use Statement 4.1 with the operation O17 and the cut vertex x'.
Thus, we may assume that no two adjacent vertices of D are both cut-vertices of G. Let v be a cut-vertex of G that belongs to D with neighbors u' and u''. Without loss of generality we may assume that color(v) = color(u'') = color(u'). Let Cu and Cu» be the components of G - v containing u' and u'', respectively. Since S = (SR, SB) is a partition of V(G) into two total dominating sets of G, there exists a neighbor of u' in Cu of the same color as u' and a neighbor of u'' in Cu» whose color is different from that of u''. Let G' be the graph obtained from G - v by identifying the vertices u' and u'' into one new vertex u, and joining u to every neighbor of u' and u''. Further, we assign to u the same color as that of u', while we change the color of all vertices in V(Cu») \ {u''} and retain the color of all vertices in V(Cu) \ {u'}. Let S' = (Sr, Sb) be the resulting partition of V(G'). We note that G' is a TDP-graph, where S' = (SR, Sr) is a partition of V(G') into two total dominating sets. We now use Statement 4.1 with the operation O17 to show that (G, S) g G, where H]1 = Cu, and H2u = Cu».	□
By Claim 4.4, we may assume that no vertex in D is a cut-vertex of G, for otherwise the desired result follows. We note that every vertex in D has one neighbor in SR and one neighbor in SB. Further, every component in G[D] is a path or a cycle.
Claim 4.5. Let C be a component of G[D]. If C is a cycle or if C is a path of order at least 5 or if C is a path of order 4 and the ends of C do not have a common neighbor, then (G, S) g G.
Proof. Suppose that C is a cycle. Since G is a connected TDP-graph, this implies that G = Cn where n = 0 (mod 4). In this case, G can be obtained from the 2-colored base graph G1 by repeated applications of operation O9 (or operation O10). Hence, we may assume that C is a path, for otherwise the desired result follows. Let C be the path x1... xk, where k > 4. Let u be the neighbor of x1 not on C. If k > 5, let v = x5, while if k = 4, let v be the neighbor of x4 not on C. By assumption, u = v. Let X = {x1,x2,x3 ,x4}.
Suppose first that color(u) = color(x1), implying that color(x2) = color(x3) = color(x4) = color(v) = color(x1). If u and v are adjacent in G, let G' = G — X. In this case, the graph G' is a TDP-graph and we use Statement 4.1 with the operation O7 to show that (G, S) G G .If u and v are not adjacent in G, let G' be obtained from G — X by adding the edge uv. Once again, the graph G' is a TDP-graph. We use Statement 4.1 with the operation O10 to show that (G, S) g G.
Suppose next that color(u) = color(x1), implying that color(x2) = color(v) = color(x3) = color(x4) = color(u). If u and v are adjacent in G, let G' = G — X. In this case, the graph G' is a TDP-graph and we use Statement 4.1 with the operation O8 to show that (G, S) G G .If u and v are not adjacent in G, let G' be obtained from G — X by adding the edge uv. Once again, the graph G' is a TDP-graph. We use Statement 4.1 with the operation O9 to show that (G, S) G G.	□
By Claim 4.5, we may assume that every component of G[D] is a path-component of order at most 4, and that the ends of a path-component of G[D] of order 4 have a common neighbor in G. In what follows we adopt the following notation. Let P be a path-component of G[D], and so P = Pk for some k G [4]. Let P be the path x1... xk, and let u and v be the vertices in G that do not belong to P and are adjacent to x1 and xk,
370
Ars Math. Contemp. 16 (2019) 277-298
respectively. We call u and v the vertices in G - V(P) associated with the path P. By assumption, if k = 4, then u = v. We note that if k = 1, then u = v. We define next a good path-component.
Definition 4.6. A path-component P of G[D] is a good path-component if P = Pk where k € [3], and both u and v have neighbors of both colors in the graph G- = G - V (P), where u and v are the vertices in G- associated with P.
Claim 4.7. If G[D] contains a good path-component, then (G, S) € G.
Proof. Suppose that G[D] contains a good path-component, P: x1... xk. By definition, k € [3]. Suppose that k =1. Since P is a good path-component, the graph G' = G - x1 is a TDP-graph. Furthermore, color(u) = color(v) since G is a TDP-graph. We now use Statement 4.1 with the operation O3 to show that (G, S) € G.
Suppose that k = 2. Suppose that color(x1) = color(x2). Then, color(u) = color(x1) and either u = v or u = v and color(u) = color(v). In both cases, since P is a good path-component, the graph G' = G - V(P) is a TDP-graph. If u = v, we use Statement 4.1 with the operation O11 to show that (G, S) € G, while if u = v, we use Statement 4.1 with the operation O4 to show that (G, S) € G. Suppose that color(x1) = color(x2). Then, color(u) = color(x1) and color(v) = color(x2). Since P is a good path-component, the graph G' = G - V (P) is a TDP-graph, and we use Statement 4.1 with the operation O5 to show that (G, S) € G.
Suppose that k = 3. Without loss of generality we may assume that color(x1) = color(x2) = color(x3), implying that color(u) = color(x1) and either u = v or u = v and color(u) = color(v). Since P is a good path-component, the graph G' = G - V(P) is a TDP-graph. If u = v, we use Statement 4.1 with the operation O12 to show that (G, S) € G, while if u = v, we use Statement 4.1 with the operation O6 to show that (G,S) € G.	□
By Claim 4.7, we may assume that G contains no good path-component, for otherwise the desired result follows. We define next an end-block path component of G[D].
Definition 4.8. A path-component P of G[D] with associated vertices u and v is an endblock path component of G[D] if u = v.
We are now in a position to present the following property of non-backtracking walks in the graph G.
Claim 4.9. Suppose that W: w1w2... wk is a non-backtracking walk in G and no vertex of W belongs to an end-block path component of G[D]. If w2 is not the only neighbor of w1 in G whose color is color(w2), then wi-1 is the only neighbor of Wj in G whose color is color(wj-1) for all i € [k] \ {1}.
Proof. Since W is a non-backtracking walk in G, we note that no two consecutive edges on W are equal; that is, wj-1 = wj+1 for all i € [k -1] \{1}. Suppose, to the contrary, that the claim is false. Let i > 2 be the smallest integer such that the vertex w^ has a neighbor different from w^-1 of the same color as w^-1.
Claim 4.9.1. i > 3.
M. A. Henning and I. Peterin: A characterization of graphs with disjoint total dominating sets 371
Proof. Renaming colors if necessary, we may assume that color(wi) = X. By supposition, at least one neighbor, say v1, of w1 different from w2 has the same color as w2. Suppose firstly that color(w2) = X. By supposition, color(v1) = X. If w2 has a neighbor, z2 say, different from w1, of color X, then either v1 = z2, in which case v1w1w2v1 is a 3-cycle in GX, or v1 = z2, in which case v1w1w2z2 is apath P4 in GX. Both cases produce a contradiction. Suppose secondly that color(w2) = X. By supposition, color(v1) = X. If w2 has a neighbor, z2 say, different from w1, of color X, then v1w1w2z2 is a path P4 in Grb , a contradiction. We deduce, therefore, that w1 is the only neighbor of w2 whose color is color(w1). Hence, i > 3.	□
By Claim 4.9.1, we have that i > 3. Renaming colors if necessary, we may assume that color(w£_1) = X .By supposition, the vertex wg has a neighbor, vg+1 say, different from of the same color as w^_1; that is, color(vg+1) = X. Further since G is a TPD-graph, the vertex wg has a neighbor of color X.
Claim 4.9.2. dG(wg_1) = 2.
Proof. Suppose that dG(w£_1) > 3. Let vg be a neighbor of w^_1 different from wg_2 and wg. Suppose that color(wg_2) = X. By the minimality of i, the vertex wg_2 is the only neighbor of wg_1 whose color is color(wg_2); that is, all neighbors of wg_1 different from wg_2 must have color X. In particular, color(vg) = color(wg) = X. Hence, vgwg_1wgvg+1 is a path P4 in GRB, a contradiction. Hence, color(wg_2) = X. Thus, all neighbors of wg_1 different from wg_2 must have color X. In particular, color(vg) = color(wg) = X .If vg = vg+1, then vgwg_1wgvg is a 3-cycle in GX, a contradiction. If vg = vg+1, then vgwg_1wgvg+1 is a path P4 in GX, a contradiction.	□
By Claim 4.9.2, the vertex wg_1 has degree 2 in G; that is, wg_1 G D. By supposition, the vertex w1 has at least two neighbors whose color is color(w2) and at least one vertex whose color is different from color(w2). In particular, the vertex w1 has degree at least 3 in G. Letp > 1 be the largest integer such that dG(wp) > 3 andp < i-2. Possibly, p = i-2. We now consider the path P: wp+1... wg_1 and note that P is a path-component in G[D]. If wp = wg, then P is an end-block path component of G[D], contradicting the supposition that no vertex of W belongs to an end-block path component of G[D]. Hence, wp = wg and the vertices wp and wg associated with the path-component P in G[D] are distinct vertices.
We now consider the graph G_ = G - V (P). By our earlier observations, the vertex wg has neighbors of both colors in G_. If p = 1, then the vertex wp has neighbors of both colors in G_. If p > 2, then by the minimality of i the vertex wp once again has neighbors of both colors in G_ . Thus the path P is a good-path component, contradicting our earlier assumption that G contains no good path-component. This completes the proof of Claim 4.9.	□
Claim 4.10. If G contains a cycle that is not an end-block of G, then (G, S) G G.
Proof. Assume that some cycle C in G is not an end-block in G. Let P be a path-component of G[D] with associated vertices u and v. Suppose firstly that u = v. Thus, P is an end-block path component of G[D] and CP = G[V(P) U {u}] is a cycle in G. Further, CP is an end-block of G with u as its cut-vertex in G. Suppose that dG (u) > 4. We now consider the graph G_ = G - V (P). By our earlier assumptions, no vertex in D is a cut-vertex of G, implying that G_ is a connected graph.
372
Ars Math. Contemp. 16 (2019) 277-298
Claim 4.10.1. The vertex u has neighbors of both colors in G .
Proof. Suppose, to the contrary, that all neighbors of u in G- have the same color. By supposition, there is a cycle C in G- that contains no vertex that belongs to an end-block component of G[D]. Hence there exists a non-backtracking walk W: ... wk in G that starts at the vertex u, proceeds from u to C, goes all the way around C, and then returns to u, without entering any end-block path component of G[D]. We note that k > 3 and that w1 = wk = u. By our supposition that all neighbors of u in G- have the same color, the vertex w2 is not the only neighbor of w1 in G whose color is color(w2). By Claim 4.9, the vertex wk-1 is the only neighbor of wk in G whose color is color(wk-1). This contradicts our supposition that all neighbors of u in G- have the same color.	□
By Claim 4.10.1, the vertex u has neighbors of both colors in G-. Since G is a TDP-graph, this implies that the graph G- is a TDP-graph. Hence, we can use Statement 4.1 with the operation O11 or O12 or O13, depending on the length of P, to show that (G, S) G G. We may therefore assume that dG(u) = 3 (and still u = v), for otherwise (G, S) G G, as desired. Thus, the vertex u has degree 1 in G-. Let x be the neighbor of u in G-. By our earlier assumptions, no vertex in D is a cut-vertex of G. In particular, the cutvertex x does not belong to D, and so dG(x) > 3. We now consider the (connected) graph G- = G- - u obtained from G- by deleting the vertex u. Using analogous arguments as in the proof of Claim 4.10.1, the vertex x has neighbors of both colors in G-. Hence, we can use Statement 4.1 with the operation O14 or O15 or O16, depending on the length of P, to show that (G, S) g G.
Suppose next that u = v. Using analogous arguments as in the proof of Claim 4.10.1, the vertices u and v each have neighbors of both colors in G-. Thus the path P is a good-path component, contradicting our earlier assumption that G contains no good path-component. This completes the proof of Claim 4.10.	□
By Claim 4.10, we may assume that every cycle in G is an end-block of G, for otherwise (G, S) G G as desired. Every block of G that is not an end-block is a copy of K2 consisting of a single edge. By our earlier assumptions, every cycle in G has length 3, 4 or 5. Let T- be the graph obtained from G by deleting all vertices that belong to an end-block path component of G[D]. By our earlier assumptions, the graph T- is a tree. In particular, every vertex of T- is a cut-vertex of G. By our earlier assumptions, no vertex in D is a cut-vertex of G, implying that every vertex of D belongs to an end-block path component of G[D]. Hence, every vertex of D belongs to an end-block of G.
Claim 4.11. If two cycles of G intersect, then (G, S) G G.
Proof. Suppose that two different cycles C1 and C2 of G intersect. Since every cycle in G is an end-block of G, these two cycles intersect in exactly one common vertex, v say.
Claim 4.11.1. If G contains exactly one cut-vertex, then (G, S) is a 2-colored base graph G3.
Proof. Suppose that G contains exactly one cut-vertex. Since the cut-vertices of G are precisely the vertices in the tree T-, this implies that V(T-) = {v}. Thus, every block of G is an end-block that contains the vertex u. Let C1 be the cycle vv1v2... vk-1v and
let color(v) = X, where k G {3,4, 5}. If k = 3, then color(v1) = color(v2) = X. If k = 4, then color(v2) = X and, renaming v1 and v3, if necessary, we may assume that
M. A. Henning and I. Peterin: A characterization of graphs with disjoint total dominating sets 373
color(vi) = X and color(v3) = X. If k = 5, then color(v2) = color(v3) = X and color(vi) = color(v4) = X.
Suppose that G contains an end-block, C say, that is a 4-cycle. If C' is an arbitrary endblock different from C, then C' - v is a good path-component of G[D], a contradiction. Hence, no end-block of G is a 4-cycle.
Thus, since G is a TDP-graph, at least one end-block is a 3-cycle and at least one endblock is a 5-cycle. Renaming the end-blocks if necessary, we may assume that C1 is a 3-cycle and C2 is a 5-cycle. These two cycles, together with their associated 2-colorings described above, form the 2-colored base graph G3. If G contains at least three blocks and C' is an arbitrary end-block different from C1 and C2, then C' - v is a good path-component of G[D], a contradiction. Hence, G contains exactly two end-blocks, implying that (G, S) is the 2-colored base graph G3.	□
By Claim 4.11.1, we may assume that G contains at least two cut-vertices, for otherwise (G, S) g G as desired. As observed earlier, the cut-vertices of G are precisely the vertices in the tree T-. Let x be a neighbor of v in T-. Renaming the cycle C1 and C2 and the vertex x if necessary, we may assume without loss of generality that the vertex v has a neighbor, y say, in C1 such that color(x) = color(y). We now consider the graph G- = G- (V(C2) \{v}). Since G is a TDP-graph, this implies that the graph G- is a TDP-graph. Hence, we can use Statement 4.1 with the operation O11 or O12 or O13, depending on the length of C2, to show that (G, S) g G.	□
By Claim 4.11, we may assume that no two cycles of G intersect, for otherwise (G, S) g G as desired. The tree T- therefore contains at least two vertices. Further, every leaf in T-has degree 3 in G and belongs to exactly one end-block of G. Let p1p2... pk be a longest path in T-. Necessarily, p1 and pk are both leaves in T-. Since T- contains no vertex of D, we note that every vertex in T- has degree at least 3 in G. Let C1 and Ck be the end-blocks in G that contain p1 and pk, respectively.
Claim 4.12. If k g {2, 3}, then (G, S) g G.
Proof. Suppose firstly that k = 2. In this case, G is obtained from the two cycles C1 and C2 by adding the edge p1p2. If C1 is a 4-cycle, then the cycle C1 together with its associated 2-coloring is the 2-colored base graph G1. Starting with this 2-colored base graph G1, we can use Statement 4.1 with the operation O14 or O15 or O16, depending on the length of C2, to show that (G, S) g G. Analogously, if C2 is a 4-cycle, (G, S) g G. Hence, we may assume that neither C1 nor C2 is a 4-cycle. With this assumption, if C1 is a 3-cycle, then C2 is also a 3-cycle noting that G is a TDP-graph. In this case, (G, S) is the 2-colored base graph G2. If C1 is a 5-cycle, then C2 is also a 5-cycle. In this case, (G, S) is the 2-colored base graph G4. Hence if k = 2, then (G, S) g G.
Suppose secondly that k = 3. We now consider the (connected) graph G- = G -V (C1). We note that the vertex p2 has degree at least 2 in G-. If the vertex p2 has neighbors of both colors in G-, then G- is a TPD-graph. In this case, we can use Statement 4.1 with the operation O14 or O15 or O16, depending on the length of C1, to show that (G, S) g G. Hence we may assume that all neighbors of p2 in G- have the same color which is different to color(p1) (noting that G is a TPD-graph). This implies that the vertex p2 has neighbors of both colors in the graph G - V (C2), and once again we can use Statement 4.1 with the operation O14 or O15 or O16, depending on the length of C2, to show that (G, S) g G. □
374
Ars Math. Contemp. 16 (2019) 277-298
By Claim 4.12, we may assume that k > 4, for otherwise (G, S) G G as desired. We now consider the (connected) graph G- = G - V(Gi). If the vertex p2 has neighbors of both colors in G-, then as in the proof of Claim 4.12 we can use Statement 4.1 with the operation Oi4 or Oi5 or Oi6, depending on the length of Gi, to show that (G, S) g G. Hence we may assume that all neighbors of p2 in G- have the same color. We now consider the walkp2p3 .. .pk. By assumption, p3 is not the only neighbor of p2 in G whose color is color(p3). By Claim 4.9, the vertexpk-2 is the only neighbor of pk-i in G whose color is color(pk-2). This implies that the vertex pk-i has neighbors of both colors in the graph G - V(C2). Hence, G - V(C2) is a TPD-graph and we can use Statement 4.1 with the operation Oi4 or Oi5 or Oi6, depending on the length of C2, to show that (G, S) g G. This completes the proof of Theorem 3.1.	□
5 Closing remarks
We remark that although our characterization in Theorem 3.1 solves a long-standing problem in the theory of total domination in graphs which has been open for several decades, it remains a challenging problem to determine in polynomial time if a given graph is a TDP-graph even for some special graph classes. Our method cannot be used to decide if a given graph G is a TDP-graph in polynomial time. The reason for that is that we have no specified vertex partition together with G. Indeed, recognizing this class of graphs is known to be NP-complete (see [8]). However, we nonetheless believe that our constructive proof gives valuable insights into the problem and gives an entirely new description of TDP-graphs, placing them in another context.
We close with a short discussion about the independence of operations Oi to Oi7 in the class G. For this purpose, we will construct small graphs in G from our 2-colored base graphs that cannot be built by any other construction in G, thereby showing that operation Oi is independent for each i g [17]. The independence of these seventeen operations used to build graphs in the family G show that none of them are redundant, and all are needed in the construction.
•	Apply operation O2 on Gi (to obtain the graph K4 - e).
•	Apply operation O3 on Gi to obtain the house graph; that is, the graph obtained from a 5-cycle by adding an edge.
•	Apply operation Oi once and operation O2 three times on the house graph to obtain K5.
•	Apply operation O4 to two nonadjacent vertices of degree 2 on G2.
•	The independence of operation Ox, where x G {5,6,11,12,13,14,15,16}, can be seen by applying Ox once on Gi.
•	The independence of operation Ox, where x G {7,10}, can be seen by applying Ox once on adjacent vertices of degree 3 in G2.
•	The independence of operation Ox, where x G {8,9}, can be seen by applying Ox once on adjacent vertices of degree 3 in G4.
•	Apply operation Oi7 once on the cut-vertex of G3.
Hence, all seventeen operations are independent. Further, our proof of Theorem 3.1 shows that all seventeen operations are necessary to give our characterization of TDP-graphs.
M. A. Henning and I. Peterin: A characterization of graphs with disjoint total dominating sets 375
References
[1]	H. Aram, S. M. Sheikholeslami and L. Volkmann, On the total domatic number of regular graphs, Trans. Comb. 1 (2012), 45-51, doi:10.22108/toc.2012.760.
[2]	B. Chen, J. H. Kim, M. Tait and J. Verstraete, On coupon colorings of graphs, Discrete Appl. Math. 193 (2015), 94-101, doi:10.1016/j.dam.2015.04.026.
[3]	E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, Total domination in graphs, Networks 10 (1980), 211-219, doi:10.1002/net.3230100304.
[4]	P. Delgado, W. J. Desormeaux and T. W. Haynes, Partitioning the vertices of a graph into two total dominating sets, Quaest. Math. 39 (2016), 863-873, doi:10.2989/16073606.2016. 1188862.
[5]	W. J. Desormeaux, T. W. Haynes and M. A. Henning, Partitioning the vertices of a cubic graph into two total dominating sets, Discrete Appl. Math. 223 (2017), 52-63, doi:10.1016/j.dam. 2017.01.032.
[6]	T. W. Haynes, S. T. Hedetniemi and P. J. Slater (eds.), Domination in Graphs: Advanced Topics, volume 209 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, New York, 1998.
[7]	T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, volume 208 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, New York, 1998.
[8]	P. Heggernes and J. A. Telle, Partitioning graphs into generalized dominating sets, Nordic J. Comput. 5 (1998), 128-142.
[9]	M. A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math. 309 (2009), 32-63, doi:10.1016/j.disc.2007.12.044.
[10]	M. A. Henning, C. Lowenstein, D. Rautenbach and J. Southey, Disjoint dominating and total dominating sets in graphs, Discrete Appl. Math. 158 (2010), 1615-1623, doi:10.1016/j.dam. 2010.06.004.
[11]	M. A. Henning and J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008), 159-162.
[12]	M. A. Henning and J. Southey, A characterization of graphs with disjoint dominating and total dominating sets, Quaest. Math. 32 (2009), 119-129, doi:10.2989/qm.2009.32.1.10.712.
[13]	M. A. Henning and A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, Springer, New York, 2013, doi:10.1007/978-1-4614-6525-6.
[14]	O. Ore, Theory of Graphs, volume 38 of American Mathematical Society Colloquium Publications, American Mathematical Society, Providence, Rhode Island, 1962.
[15]	J. Southey and M. A. Henning, A characterization of graphs with disjoint dominating and paired-dominating sets, J. Comb. Optim. 22 (2011), 217-234, doi:10.1007/ s10878-009-9274-1.
[16]	B. Zelinka, Total domatic number and degrees of vertices of a graph, Math. Slovaca 39 (1989), 7-11.