ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 209–222
https://doi.org/10.26493/1855-3974.2465.571
(Also available at http://amc-journal.eu)
Well-totally-dominated graphs*
Selim Bahadır
Department of Mathematics, Ankara Yıldırım Beyazıt University, Ankara, Turkey
Tınaz Ekim
Department of Industrial Engineering, Boğaziçi University, İstanbul, Turkey
Didem Gözüpek
Department of Computer Engineering, Gebze Technical University, Kocaeli, Turkey
Received 22 October 2020, accepted 19 February 2021, published online 29 October 2021
Abstract
A subset of vertices in a graph is called a total dominating set if every vertex of the
graph is adjacent to at least one vertex of this set. A total dominating set is called minimal
if it does not properly contain another total dominating set. In this paper, we study graphs
whose all minimal total dominating sets have the same size, referred to as well-totally-
dominated (WTD) graphs. We first show that WTD graphs with bounded total domination
number can be recognized in polynomial time. Then we focus on WTD graphs with total
domination number two. In this case, we characterize triangle-free WTD graphs and WTD
graphs with packing number two, and we show that there are only finitely many planar
WTD graphs with minimum degree at least three. Lastly, we show that if the minimum
degree is at least three then the girth of a WTD graph is at most 12. We conclude with
several open questions.
Keywords: Total domination, well-totally-dominated graphs, minimal total dominating sets.
Math. Subj. Class. (2020): 05C69
*This work has been supported by the Scientific and Technological Research Council of Turkey (TUBITAK)
under grant no. 118E799. The work of Didem Gözüpek was also supported by the BAGEP Award of the Science
Academy of Turkey.
E-mail addresses: sbahadir@ybu.edu.tr (Selim Bahadır), tinaz.ekim@boun.edu.tr (Tınaz Ekim),
didem.gozupek@gtu.edu.tr (Didem Gözüpek)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
210 Ars Math. Contemp. 20 (2021) 209–222
1 Introduction
Total domination in graphs has been extensively studied in the literature (see [15]) and has
numerous applications. For instance, consider a computer network where a core group of
file servers has the ability to communicate directly with every computer outside the core
group. Moreover, each file server is directly linked to at least one other backup file server
where duplicate information is stored. This core group of servers corresponds to a total
dominating set in the graph representing the computer network. Another application area
is a specific committee selection mechanism such that every non-member of the committee
knows at least one member of the committee and every member of the committee knows
at least one other member of the committee to avoid feelings of isolation and thus enhance
cooperation (see [14]).
Let G be a graph with no isolated vertices. A subset S of V (G) is called a total dom-
inating set (TDS) of G if every vertex in G is adjacent to at least one element in S. A
total dominating set is minimal if it contains no other TDS of G. The minimum size of a
total dominating set of a graph G is called the total domination number and denoted by
γt(G), while the maximum size of a minimal total dominating set is called the upper total
domination number and denoted by Γt(G). G is called well-totally-dominated (WTD) if
every minimal TDS of G is of the same size, that is, γt(G) = Γt(G). WTD graphs with
γt = k are denoted by WTD(k).
Given a graph, computing its total domination number and its upper total domination
number are NP-hard in general [6, 18] and already NP-hard even in specific graph classes
such as bipartite graphs, comparability graphs and claw-free graphs [15]. One way to deal
with such a problem is to consider “trivial” instances where these two paramaters have the
same value. Examples of graph classes defined in this way in the literature include well-
covered graphs (whose all maximal independent sets have the same size), well-dominated
graphs (whose all minimal dominating sets have the same size), and equimatchable graphs
(whose all maximal matchings have the same size). Structural properties of each one of
these graph classes have been studied extensively in the literature. In this paper, we take
the same approach for the total dominating sets. Works on total domination in the literature
mostly focused on the relation of the total domination number with other graph parame-
ters and characterized graphs with total domination number being equal to an upper bound
(e.g. [3, 4]). Inequalities relating the total domination number to other domination param-
eters and characterization of graphs that tightly attain these bounds have also been studied
(see [1, 16]).
Clearly, if the total domination number and the upper total domination number are
polynomial time solvable for a given class of graphs, then the recognition of WTD graphs
belonging to this class of graphs is polynomial. However, the complexity of recognizing
WTD graphs in general is unknown. In such a situation, a classical approach consists in
studying the structure of WTD graphs in restricted graph classes and providing structural
characterizations along with efficient recognition algorithms whenever possible.
WTD graphs were initially introduced in [12], where WTD cycles and paths are char-
acterized and several constructions of WTD trees are given. They also proved that a WTD
graph with minimum degree at least two has girth at most 14. The work in [7] focused
on the composition and decomposition of WTD trees and proved that any WTD tree can
be constructed from a family of three small trees. To the best of our knowledge, [12] and
[7] are the only work on WTD graphs. A graph class resembling WTD graphs is well-
dominated graphs, which are graphs whose minimal dominating sets have the same size. It
S. Bahadır et al.: Well-totally-dominated graphs 211
is known that well-dominated graphs form a proper subset of well-covered graphs [8]. We
note that well-covered graphs are graphs whose maximal independent sets have the same
size and there is a rich literature about them (see [13, 19]). Well-dominated graphs were in-
troduced by Finbow et al. [8], who provided a characterization of bipartite well-dominated
graphs and well-dominated graphs with girth at least 5. Characterizations of these graphs
within other graph classes were also obtained [9, 10, 17, 20]. Although their definitions re-
semble each other, there is not a containment relationship between WTD graphs and well-
dominated graphs. For instance, a cycle on six vertices is WTD but not well-dominated,
whereas the graph T10 described in [17] is well-dominated but not WTD.
It follows from the previous studies on WTD graphs that we do not know much about
their structure. In this paper, we investigate the study of WTD graphs from a structural
point of view. We first study WTD graphs with bounded total domination number. We
prove in Section 2 that the recognition of WTD graphs with total domination number k is
solvable in polynomial time for every positive integer k. We then focus on WTD graphs
with total domination number 2, referred to as WTD(2) graphs in Section 3. We char-
acterize triangle-free WTD(2) graphs and WTD(2) graphs with packing number 2 (or
equivalently of diameter 3). We also show that there is a finite number of planar WTD(2)
graphs with minimum degree at least 3. Subsequently, we study the girth of WTD graphs in
Section 4. In particular, building on a result in [12], we prove that WTD graphs with mini-
mum degree at least three have girth at most 12. Finally, we discuss several open research
directions.
2 WTD graphs with bounded total domination number
Recall that the complexity of recognizing WTD graphs is unknown. In this section, we
show that for any positive integer k, WTD(k) graphs can be recognized in polynomial time.
To this end, we will use an equivalent description of WTD(k) graphs using transversal
hypergraphs. Let us first introduce necessary definitions. A hypergraph H is a pair H =
(X,E) where X is a set of elements called vertices, and E is a set of nonempty subsets
of X called hyperedges. Therefore, a hypergraph might have a vertex which belongs to
none of the hyperedges, but cannot have multiple hyperedges. A transversal (or hitting set)
of a hypergraph H = (X,E) is a set T ⊆ X that has nonempty intersection with every
hyperedge of H . A transversal of a collection of sets is a transversal of the hypergraph
whose hyperedges are the given collection. A transversal T is called minimal if no proper
subset of T is a transversal. The transversal hypergraph of H = (X,E) is the hypergraph
H∗ = (X,F ) whose hyperedge set F consists of all minimal transversals of H .
Let G be a graph with no isolated vertex. Let HG be the hypergraph whose vertex set
is V (G) and hyperedges are open neighborhoods of the vertices of G. Let also MTDS(G)
denote the set of all minimal total dominating sets of G.
Lemma 2.1. MTDS(G) consists of hyperedges of the transversal hypergraph of HG.
Proof. Let T be a hyperedge of H∗G, that is a minimal transversal of the set of open neigh-
borhoods of G. This means that T contains a neighbor of every vertex in G, thus it is a total
dominating set. By minimality of the transversal T , it is also a minimal total dominating set
of G. Conversely, let S be a minimal total dominating set of G. Then, every vertex in G is
adjacent to at least one vertex in S. That is, S has a nonempty intersection with every open
neighborhood in G. Therefore, S is a transversal of the hypergraph HG and minimality of
S implies that it is a minimal transversal. Thus, S is a hyperedge of H∗G.
212 Ars Math. Contemp. 20 (2021) 209–222
Proposition 2.2. Let G be a graph. Then, for any minimal transversal T of MTDS(G),
there exists a vertex v in G such that N(v) = T .
Proof. Let MTDS(G) = {A1, . . . , Am}. Since T has nonempty intersection with each
Ai, V (G) \ T contains none of the minimal total dominating sets A1, . . . , Am. Therefore,
V (G) \ T is not a TDS of G, and hence there exists at least one vertex v ∈ V (G) such that
N(v) ∩ (V (G) \ T ) = ∅. Thus, we see that N(v) ⊆ T . Suppose that N(v) ̸= T . Then
T \N(v) ̸= ∅ and let u ∈ T \N(v). Since T is a minimal transversal, T \ {u} is disjoint
with at least one of A1, . . . , Am, say A1. As u ∈ T \ N(v), we have N(v) ⊆ T \ {u},
and hence N(v) ∩ A1 = ∅. That is, v is not dominated by A1, which is a contradiction.
Therefore, N(v) = T .
A hypergraph H is said to be Sperner if no hyperedge of H contains another hyperedge.
The following result shows that any finite collection of finite sets which forms a Sperner
hypergraph corresponds to the set of all minimal total dominating sets of a graph.
Proposition 2.3. Let H be a Sperner hypergraph. Then there exists a graph G such that
E(H) = MTDS(G).
Proof. Let E(H) = {A1, . . . , Am} and A = ∪mi=1Ai. Consider a graph with vertex set A
and draw edges between its vertices such that each vertex is adjacent to at least one vertex
in Ai for all i = 1, . . . ,m (for example, draw all possible edges). Then, in accordance with
Proposition 2.2, for each minimal transversal T of H , add a vertex vT to the graph such
that N(vT ) = T . Let G be the resulting graph.
We first show that each Ai is a TDS of G. By construction, every vertex of A is adjacent
to at least one vertex in Ai. Moreover, for every minimal transversal T of A1, . . . , Am we
have T ∩ Ai ̸= ∅, and hence, each vT is dominated by Ai. Therefore, Ai is a TDS for
i = 1, . . . ,m.
We next show that every TDS of G contains at least one of A1, . . . , Am. Let S be a
TDS of G and suppose that Ai ⊈ S for i = 1, . . . ,m. Then, V (G) \ S is a transversal
of A1, . . . , Am, and hence, there exists a minimal transversal T of A1, . . . , Am such that
T ⊆ V (G) \ S. On the other hand, we have N(vT ) = T and thus, we get N(vT )∩ S = ∅,
which contradicts that S is a TDS of G.
Consequently, a set other than A1, . . . , Am can not be a minimal TDS of G. We finally
show that each Ai is a minimal TDS of G. Suppose that Ai is not minimal for some i.
Then, Ai \{x} is still a TDS of G for some x ∈ Ai, and therefore, Aj ⊆ Ai \{x} for some
j, which implies Aj ⊆ Ai contradicting that H is Sperner. Therefore, minimal TDSs of G
are exactly A1, . . . , Am.
Remark 2.4. One can extend G to another graph whose minimal TDSs are A1, . . . , Am
as follows: Let G′ be a graph disjoint from G. Draw edges between the vertices of G′
and A in such a way that every vertex of G′ is adjacent to at least one vertex of Ai for
i = 1, . . . ,m. By following the same arguments, it is easy to check that minimal TDSs of
the resulting graph are A1, . . . , Am.
Notice that any finite collection consisting of distinct sets of size k corresponds to a
Sperner hypergraph and therefore, Proposition 2.3 implies the following result.
Corollary 2.5. For every integer k ≥ 2, WTD(k) is an infinite graph family.
S. Bahadır et al.: Well-totally-dominated graphs 213
The HYPERGRAPH TRANSVERSAL problem is the decision problem that takes as input
two Sperner hypergraphs H and H ′ and asks whether H ′ is the transversal hypergraph H∗
of H .
Theorem 2.6 ([2, 5]). For every positive integer k, the HYPERGRAPH TRANSVERSAL
problem is solvable in polynomial time if all hyperedges of one of the two hypergraphs H
and H ′ are of size at most k.
Theorem 2.6 has the following consequence:
Corollary 2.7 ([11]). For every positive integer k, the following problem is solvable in
polynomial time: Given a Sperner hypergraph H , determine whether all minimal transver-
sals of H are of size k.
The complexity of recognition of WTD graphs with bounded total domination number
can now be derived from Corollary 2.7.
Theorem 2.8. For every positive integer k, the problem of recognizing WTD(k) graphs
can be solved in polynomial time.
Proof. Let G be a graph with no isolated vertices. Consider the hypergraph HG = (V, E),
where E contains the inclusion-minimal elements of {N(v) : v ∈ V }. Observe that HG is
Sperner and that the minimal transversals of HG are exactly the minimal total dominating
sets of G by Lemma 2.1. It follows that G is WTD if and only if all minimal transversals
of HG are of size k. By Corollary 2.7, this condition can be tested in polynomial time.
3 WTD graphs with total domination number two
In this section, we study WTD graphs whose total domination number is 2. We give
complete characterizations of WTD(2) graphs with packing number 2 and triangle-free
WTD(2) graphs. We also show that planar WTD(2) graphs with minimum degree at least
3 have at most 16 vertices.
Let G be a WTD(2) graph. Note that every minimal TDS of G is a pair consisting
of endpoints of an edge of G. Consequently, every WTD(2) graph is connected. We
will call an edge of G whose endpoints is a TDS of G a dominating edge of G. Let Gde
be the graph with vertex set ∪S∈MTDS(G)S (i.e., vertices of G serve as an endpoint of a
dominating edge) and edge set which consists of dominating edges of G. In other words,
Gde is the edge-induced subgraph of G obtained by the dominating edges. See Figure 1 for
an example.
G
x
y
z
t
w
y
z
t
w
Gde
Figure 1: A WTD(2) graph G and the graph Gde obtained by the dominating edges of G.
214 Ars Math. Contemp. 20 (2021) 209–222
Remark 3.1. Notice that the graph Gde and the subgraph of G induced by V (Gde) are not
necessarily the same. In general, Gde is a subgraph of G but not necessarily an induced
subgraph of G with respect to a set of vertices.
A set S is a vertex cover of a graph G if every edge of G has an endpoint from S. Let
MVC(G) denote the set of all minimal vertex covers of the graph G.
Proposition 3.2. Let G be a WTD(2) graph. For every minimal vertex cover S of Gde
there exists a vertex vS in G such that N(vS) = S.
Proof. We notice that every minimal vertex cover S of Gde is a minimal transversal of
MTDS(G). Therefore, by Proposition 2.2 there exists a vertex in G whose neighborhood
is exactly S.
3.1 Characterization of WTD(2) graphs with packing number 2
A set S ⊆ V (G) is called a packing of G if N [u] ∩N [v] = ∅ for every distinct u, v ∈ S.
The packing number ρ(G) is the maximum size of a packing of G. It is well-known that
for any graph G we have ρ(G) ≤ γ(G) ≤ γt(G). Therefore, if γt(G) = 2, then ρ(G) is
either 1 or 2. In this subsection, we provide a characterization of WTD(2) graphs G with
ρ(G) = 2. In particular, this characterization allows us to construct any WTD(2) graph
with ρ(G) = 2.
Let W2 be the set of graphs obtained as follows:
Step 1: Choose a bipartite graph H with no isolated vertices.
Step 2: For every S ∈ MVC(H), choose a new vertex vS and draw edges from vS to
every vertex in S.
Step 3: For each edge uv in H and every w ∈ V (H) \ {u, v}, add the edges wu and/or
wv if needed to make sure w is adjacent to at least one of u and v.
Step 4: Choose a new graph H ′ (might be the empty graph) which is disjoint from the
current graph. Then for each edge uv in H and every w ∈ V (H ′), draw at least
one of the edges wu and wv.
A graph in W2 is given in Figure 2.
H
Step 2
v{x,z}
v{x,t} v{y,z}
v{y,t}
x y
z t
x y
z t
Step 3
v{x,z}
v{x,t} v{y,z}
v{y,t}
x y
z t
Step 4
v{x,z}
v{x,t} v{y,z}
v{y,t}
x y
z t
u1 u2
u3
Figure 2: A graph in W2 obtained by the given process. Bold edges represent the dominat-
ing edges.
S. Bahadır et al.: Well-totally-dominated graphs 215
Lemma 3.3. If a graph G is in W2, then G is a WTD(2) graph with ρ(G) = 2.
Proof. Let G ∈ W2 and H = (U, V,E) be the bipartite graph in the first step of the
construction of G. We first show that the packing number of G is 2. As H has no isolated
vertices, both U and V are minimal vertex covers of H . Thus, the vertices vU and vV
have disjoint closed neighborhoods since N(vU ) = U and N(vV ) = V and hence, we get
ρ(G) ≥ 2. Clearly, by construction, every edge of H is a dominating edge of G. Therefore,
we get γt(G) = 2. Since ρ(G) ≤ γt(G), we obtain ρ(G) ≤ 2 and hence, ρ(G) = 2.
Now let T be a minimal TDS of G other than the edges of H . Then T contains at
most one endpoint of an edge of H because otherwise T contains a TDS, which contradicts
that T is minimal. Therefore, V (H) \ T is a vertex cover of H and hence, it contains a
minimal vertex cover S of H . By construction there exists a vertex vS with N(vS) = S.
As S ⊆ V (H) \ T , we obtain N(vS) ∩ T = ∅, which contradicts that T is a TDS of G.
Consequently, edges of H are the only minimal TDSs of G and hence, G is a WTD(2)
graph and Gde = H .
Lemma 3.4. Let G be a WTD(2) graph with ρ(G) = 2. Then, G is in W2.
Proof. Let {x, y} be a packing with minimum |N [x]|+ |N [y]|. Note that every dominating
edge of G has one endpoint from N(x) and one from N(y) and hence, Gde is a bipartite
graph, say with parts X and Y where X ⊆ N(x) and Y ⊆ N(y).
We next show that X = N(x) and Y = N(y). By symmetry, it suffices to prove
X = N(x). Notice that Gde has no isolated vertices and therefore, X is a minimal vertex
cover of Gde. By Proposition 3.2 there exists a vertex vX satisfying N(vX) = X . Suppose
that X ̸= N(x). Then, we get X ⊂ N(x). Clearly vX ̸= y. Moreover, vX /∈ N(y)
since y /∈ X = N(vX). Thus, we get N [vX ] ∩N [y] = ∅ and hence {vX , y} is a packing
of G. However, we obtain |N [vX ]| + |N [y]| < |N [x]| + |N [y]| since X ⊂ N(x), which
contradicts the definition of the packing {x, y}. Consequently, we get X = N(x) and
hence, we may take vX = x. Similarly, we have Y = N(y) and we may assume vY = y.
Now let S be a minimal vertex cover of Gde. By Proposition 3.2 there exists a vertex vS
satisfying N(vS) = S. If S = X or S = Y , we can take vS to be x or y, respectively, and
in both cases, we have vS /∈ V (Gde). Otherwise, suppose that vS ∈ V (Gde) = X ∪ Y .
Without loss of generality, let vS ∈ X . Then, as X = N(x), we get x ∈ N(vS) =
S ⊆ N(x) ∪N(y), which is a contradiction. Therefore, vS is not a vertex of Gde, that is,
vS ∈ V (G) \ V (Gde).
Finally, we see that one can obtain the graph G by following the procedure in the
definition of W2 with the initial bipartite graph H = Gde.
Combining the results in Lemma 3.3 and Lemma 3.4 gives the following structural
characterization of WTD(2) graphs with ρ(G) = 2. Moreover, by definition of the class
W2, this provides us with a procedure to construct any WTD(2) graph with ρ(G) = 2.
Theorem 3.5. A graph G is WTD(2) with ρ(G) = 2 if and only if G ∈ W2.
Given a graph G, the diameter of G, denoted by diam(G) is the maximum length of
a shortest path between any pair of vertices of G. Let G be a graph such that γt(G) = 2.
Then, it is easy to see that diam(G) ≤ 3. Moreover, whenever γt(G) = 2, we have
diam(G) = 3 if and only if ρ(G) = 2 and therefore, in all the statements in Lemma 3.3,
Lemma 3.4 and Theorem 3.5, the condition ρ(G) = 2 can be replaced with diam(G) = 3.
216 Ars Math. Contemp. 20 (2021) 209–222
Corollary 3.6. A graph G is WTD(2) with diam(G) = 3 if and only if G ∈ W2.
One may attempt to modify the description of W2 graphs in order to describe all
WTD(2) graphs with ρ(G) = 1. In the first step of the process of building a graph in
W2, if one starts with a non-bipartite graph H with no isolated vertices, then the resulting
graph is still WTD(2) but has packing number 1. However, not every WTD(2) graph G
with ρ(G) = 1 can be obtained in this way. For example, consider the graph presented in
Figure 1. To obtain this graph G, in Step 1 one should definitely choose H to be the graph
with vertex set {z, y, t, w} and edge set {zy, yt, tw} which is indeed Gde. However, in
Step 2 if one chooses a new vertex vS for S = {y, w} (which is a minimal vertex cover of
Gde), then the graph G can not be obtained. So, the complete characterization of WTD(2)
graphs with ρ(G) = 1 is left as an open question.
3.2 Triangle-free WTD(2) graphs
In this subsection, we provide characterization of triangle-free WTD(2) graphs.
Lemma 3.7. If G is a triangle-free graph with γt(G) = 2, then G is a bipartite graph and
we have
ρ(G) =
{
1, if G is complete bipartite;
2, otherwise.
Proof. Let uv be a dominating edge of G. Then we have N(u) ∪ N(v) = V (G). As
G is triangle-free, none of two adjacent vertices have a common neighbor. Therefore,
we have N(u) ∩ N(v) = ∅ and also see that both N(u) and N(v) are independent sets.
We consequently obtain that G is a bipartite graph with parts N(u) and N(v). Since
ρ(G) ≤ γt(G) = 2, we have ρ(G) ∈ {1, 2}. Moreover, it is clear that ρ(G) = 1 if and
only if each vertex in N(u) is adjacent to all the vertices in N(v), i.e., G is a complete
bipartite graph.
For a bipartite graph with parts X and Y , define Xu = {x ∈ X : N(x) = Y } and
Yu = {y ∈ Y : N(y) = X}. In other words, Xu (resp. Yu) is the set of vertices in X (resp.
Y ) which are adjacent to every vertex in Y (resp. X). The following result characterizes
all triangle-free WTD(2) graphs.
Theorem 3.8. The following three statements are equivalent:
(i) G is a triangle-free WTD(2) graph.
(ii) G is a bipartite WTD(2) graph.
(iii) G is complete bipartite graph or G is a bipartite graph with parts X and Y such
that there exist vertices a ∈ X \Xu and b ∈ Y \ Yu satisfying N(a) = Yu ̸= ∅ and
N(b) = Xu ̸= ∅.
Proof. By Lemma 3.7 we see that (i) implies (ii). On the other hand, the implication
(iii) ⇒ (i) can be easily verified and hence, the proof finishes if we show that (ii) implies
(iii). Now let G be a bipartite WTD(2) graph, say with parts X and Y . Clearly we will
only consider the case when G is not a complete bipartite graph. By definition of Xu and
Yu, note that every dominating edge of G has one endpoint in Xu ̸= ∅ and one endpoint
in Yu ̸= ∅. Moreover, any edge xy where x ∈ Xu and y ∈ Yu is a dominating edge of G.
S. Bahadır et al.: Well-totally-dominated graphs 217
Therefore, Gde is the subgraph of G induced by Xu∪Yu and it is complete bipartite. Thus,
Gde has only two minimal vertex covers, namely Xu and Yu. Then, definition of a graph
in W2 and Theorem 3.5 imply the existence of the vertices a ∈ X \ Xu and b ∈ Y \ Yu
with N(a) = Yu and N(b) = Xu.
Although a polynomial time recognition algorithm for WTD(2) graphs follows from
Theorem 2.8, the characterization in Theorem 3.8 provides us with a simple linear time
recognition algorithm.
Corollary 3.9. Triangle-free WTD(2) graphs can be recognized in linear time.
Proof. Given a graph G, one can check whether it is a connected bipartite graph and if so,
find its unique bipartition (X,Y ) in linear time (in the number of vertices and edges of G).
Then, sets Xu and Yu can be identified simply by assigning every vertex x ∈ X such that
d(x) = |Y | into Xu, and y ∈ Y such that d(y) = |X| into Yu. According to Theorem 3.8,
G is triangle-free WTD(2) if and only if either Xu = X and Yu = Y (thus, G is complete
bipartite), or the removal of Xu and Yu leaves at least one isolated vertex in each one of X
and Y . Clearly, all these checks take only linear time.
3.3 Planar WTD(2) graphs
In this subsection, we study planar WTD(2) graphs whose minimum degree is at least
three and show that such graphs can have at most sixteen vertices. Throughout this section,
we frequently use the fact that a graph obtained by an edge contraction of a planar graph is
also planar. Recall also that a planar graph contains no K5 or K3,3.
Observation 3.10. Let G be a WTD(2) graph. The vertex obtained by edge contraction
of a dominating edge is a universal vertex in the new graph.
Let ν(G) denote the matching number of a graph G.
Lemma 3.11. Let G be a planar WTD(2) graph. If ν(Gde) ≥ 3, then |V (G)| ≤ 8.
Proof. Suppose that ν(Gde) ≥ 3 and G has at least 9 vertices. Then, G has three inde-
pendent dominating edges, say u1v1, u2v2 and u3v3, and three vertices other than u1, u2,
u3, v1, v2, v3, say w1, w2 and w3. Now contract the edges u1v1, u2v2 and u3v3. In the
resulting graph, new three vertices and w1, w2, w3 contain a K3,3, which contradicts the
planarity.
Lemma 3.12. If G is a WTD(2) graph with δ(G) ≥ 3, then ν(Gde) ≥ 2.
Proof. Let G be a WTD(2) graph with δ(G) ≥ 3. It suffices to show that G has two
independent dominating edges. Let xy be a dominating edge of G. Since the minimum
degree is at least three, each vertex of G has at least one neighbor in V (G) \ {x, y}. There-
fore, V (G) \ {x, y} is a TDS of G and hence, it contains a dominating edge ab since G is
WTD(2). As the dominating edges xy and ab share no vertex, we get ν(Gde) ≥ 2.
Combining the results in Lemmas 3.11 and 3.12 gives the following result.
Proposition 3.13. If G is a planar WTD(2) graph with δ(G) ≥ 3, then ν(Gde) = 2 or
|V (G)| ≤ 8.
218 Ars Math. Contemp. 20 (2021) 209–222
We next study planar WTD(2) graphs whose minimum degree is at least 3 and match-
ing number is 2.
Proposition 3.14. If G is a planar WTD(2) graph with δ(G) ≥ 3 and ν(Gde) = 2, then
|V (G)| ≤ 16.
Proof. Let ab and xy be two independent dominating edges of G and H = G−{a, b, x, y}.
Let H1, . . . ,Hm be the connected components of H and order of Hi be hi for i =
1, . . . ,m. Note that it suffices to show that h1 + · · ·+ hm ≤ 12.
We first prove that each Hi is a path or a singleton. Note that it suffices to show that
maximum degree of H is at most 2 and H contains no cycle. Suppose that a vertex v of
H has three neighbors, say v1, v2, v3, in H . Then contraction of the edges ab and xy gives
rise to a K3,3 with parts {ab, xy, v} and {v1, v2, v3}, which is a contradiction. Therefore,
every vertex in H has at most two neighbors in H . Suppose that H has a cycle, say
v1, v2, . . . , vk. Contract the edge vkvk−1 and denote the new point by vk−1. Then contract
the edge vk−1vk−2 and denote the new point by vk−2 and so on. Follow this process until
we get a triangle v1, v2, v3. Then contracting the edges ab and xy yields a K5 with vertices
ab, xy, v1, v2, v3, which is a contradiction. Thus, H has no cycle and hence, H is a disjoint
union of paths and singletons.
We next show that for every vertex u ∈ H we have |N(u) ∩ {a, b, x, y}| ≥ 3 or
|(N(u) ∪N(v)) ∩ {a, b, x, y}| ≥ 3 for some neighbor v ∈ V (H) of u. Since both ab and
xy are dominating edges, the intersection N(u) ∩ {a, b, x, y} has at least two elements:
one from {a, b} and one from {x, y}. Consider the case when |N(u) ∩ {a, b, x, y}| = 2.
Without loss of generality, let N(u) ∩ {a, b, x, y} = {a, x}. Since the minimum degree of
G is at least 3, there is no vertex v ∈ G such that N(v) = {a, x}. Hence, by Proposition 3.2
the set {a, x} is not a vertex cover of Gde. Then, there exists an edge wv of Gde such that
{w, v} ∩ {a, x} = ∅. Thus, as ν(Gde) = 2 and ab, xy ∈ Gde, we have wv = by or
w ∈ {b, y} and v ∈ V (H). Recall that wv is a dominating edge in G and hence, u is
adjacent to w or v. Therefore, the case wv = by is impossible and we see that v is adjacent
to u. Consequently, we get |(N(u) ∪ N(v)) ∩ {a, b, x, y}| ≥ 3 since w ∈ {b, y} is a
neighbor of v. Note that this result implies that if {u} is a component of H , then u has at
least three neighbors among a, b, x, y; otherwise, contraction of the edge uv gives rise to a
vertex adjacent to at least three of a, b, x, y.
We then apply the following process for each i = 1, . . . ,m: If hi ≤ 3, contract the
edges of Hi and obtain a singleton. If hi ≥ 4, let Hi be the path v1, v2, . . . , vk where
k = hi. First, contract v1v2 and vk−1vk. Then contract the paths v3v4v5, v6v7v8, . . .
and so on. Note that for every i we obtain at least 2 + ⌊(hi − 4)/3⌋ = ⌊(hi + 2)/3⌋
vertices adjacent to at least three of a, b, x, y. Therefore, each such vertex is adjacent to
both a and b or adjacent to both x and y. Assume that the number of vertices having
at least three neighbors among a, b, x, y in the resulting graph is more than 4. Then, by
pigeonhole principle, there will be three distinct vertices u1, u2 and u3 each of which is
adjacent, without loss of generality, to both a and b. Then, contraction of the edge xy gives
a K3,3 with parts {a, b, xy} and {u1, u2, u3}, contradicting the planarity of G. Thus, there
are at most 4 vertices having at least three neighbors among a, b, x, y once the contraction
process is terminated, that is,
∑m
i=1⌊(hi +2)/3⌋ ≤ 4. Since hi is an integer, the inequality
hi/3 ≤ ⌊(hi + 2)/3⌋ holds, implying that
∑m
i=1 hi/3 ≤ 4 which yields
∑m
i=1 hi ≤ 12 as
desired.
S. Bahadır et al.: Well-totally-dominated graphs 219
Propositions 3.13 and 3.14 imply that, unlike the general case stated in Corollary 2.5,
there is a finite number of planar WTD(2) graphs with δ(G) ≥ 3.
Theorem 3.15. If G is a planar WTD(2) graph with δ(G) ≥ 3, then |V (G)| ≤ 16.
In contrast, there is no upper bound on the number of vertices for planar WTD(2)
graphs with minimum degree 1 or 2. For example, consider a star with arbitrarily many
leaves and a graph with arbitrarily many triangles sharing a common edge, respectively.
4 Girth of WTD graphs
In this section, we provide a relation between the minimum degree and the girth for WTD
graphs. We show that if the minimum degree is more than two in a WTD graph, then the
graph contains a cycle of length at most twelve. It is shown in [12] that if G is a WTD
graph with δ(G) ≥ 2, then the girth of G, g(G), is at most 14.
Theorem 4.1 ([12, Theorem 4.1]). Suppose G is a connected graph with no leaves such
that G has girth at least fifteen. Then γt(G) < Γt(G).
By following the idea in the proof of Theorem 4.1 in [12], one can find other relations
between δ(G) and g(G) of a WTD graph G. Before presenting such extensions, we need
the following useful lemma, which is also given in [12]:
Lemma 4.2. Let G be a WTD graph, u1v1, . . . , umvm be a subset of the edges of G and
A = ∪mi=1{ui, vi}. If the subgraph of G induced by A is disjoint union of m complete
graphs of order 2 and G−N [A] has no isolated vertices, then G−N [A] is also WTD.
Proof. Let S be a minimal TDS of G −N [A]. We claim that S ∪ A is a minimal TDS of
G. It is easy to see that it is a TDS of G. Suppose that S ∪ A contains another TDS of G,
say T . Then T ∩S is a TDS of G−N [A] and hence, since S is minimal we get T ∩S = S.
Therefore, we obtain T = S ∪A′ where A′ ⊆ A. If A \A′ is nonempty, then without loss
of generality we assume that u1 ∈ A \ A′. But then, v1 is not dominated by T , which is a
contradiction. Therefore, we have A′ = A, which implies that T = S ∪ A, that is, S ∪ A
is minimal.
As every minimal TDS of G has the same size, |S|+2m is independent of S and hence,
G−N [A] is a WTD graph as well.
Theorem 4.3. If G is a WTD graph with δ(G) ≥ 3, then g(G) ≤ 12.
Proof. Assume that G is a WTD graph with δ(G) ≥ 3 and g(G) ≥ 13. Let P =
v1, v2, v3, v4, v5 be a path in G. For any vertex v in G, let dP (v) = min1≤i≤5 dist(v, vi).
Define Nk to be the set of vertices v with dP (v) = k for k = 1, 2, . . . .
First note that every vertex in Nk has a neighbor in Nk−1 for every k ≥ 2. Moreover,
for k = 1, 2, 3, Nk is an independent set since otherwise we obtain a cycle of length at most
11. We will now show that for k = 1, . . . , 4, any vertex in Nk has at least one neighbor in
Nk+1. Suppose that there exist k ≤ 4 and v ∈ Nk such that v is adjacent to no vertex in
Nk+1. By definition, it is clear that v has no neighbor in Nl for any l ≥ k + 2. Therefore,
all the neighbors of v are in ∪1≤i≤kNi. Thus, as v has at least three neighbors, there exist
three paths from v to P such that one of them has length k and two of them have length at
most k + 1. By a simple case analysis, considering the vertices of these paths on P gives
that there exist a cycle of length at most 2k + 3 ≤ 11, which is a contradiction.
220 Ars Math. Contemp. 20 (2021) 209–222
Now, let N2 = {w1, . . . , wm}. For every i = 1, . . . ,m, choose a neighbor of wi in N3,
say ui. Let A = ∪mi=1{wi, ui}. For any i ̸= j, wi is not adjacent to uj because otherwise
we obtain a cycle of length at most 10. Therefore, the induced subgraph of G induced by
A is a disjoint union of m complete graphs of order 2.
Next, consider the graph H = G −N [A]. Note that N [A] consists of N1, N2, N3 and
some vertices in N4. Therefore, P is a connected component of H . As any vertex in N4
has a neighbor in N5, no vertex v ∈ N4 ∩ V (H) is isolated in H . Clearly, no vertex in
Nk with k ≥ 6 is isolated in H since it has a neighbor in Nk−1. Suppose to the contrary
that a vertex v in N5 is isolated in H . Then v has no neighbor in N5 and N6, and thus, all
its neighbors are in N4. Therefore, since there exist three paths from v to P , this yields
a cycle of length at most 12, which is a contradiction. Consequently, H has no isolated
vertices and we can apply Lemma 4.2 and conclude that H is a WTD graph. However, P
is a component of H and hence, it should be WTD as well. Nevertheless, a path of length 4
is not a WTD graph (both {v1, v2, v4, v5} and {v2, v3, v4} are minimal TDSs of P ), which
is a contradiction.
5 Conclusion
In this work, we studied graphs whose all minimal total dominating sets have the same size.
We say these graphs are well-totally-dominated. We proved that well-totally-dominated
graphs with bounded total domination number can be recognized in polynomial time. We
then analyzed well-totally-dominated graphs with total domination number two for the
special cases of triangle-free graphs and planar graphs. Finally, we focused on the girth
of well-totally-dominated graphs. In particular, we proved that a well-totally-dominated
graph with minimum degree at least three has girth at most 12. We now conclude with
several future research directions.
Although we proved in this paper that the problem of recognizing well-totally-dominated
graphs with bounded total domination number can be solved in polynomial time, the com-
plexity of the general case is an open research problem. Hence, we pose the following
question:
Problem 5.1. What is the computational complexity of recognizing well-totally-dominated
graphs?
We have already characterized WTD(2) graphs with packing number ρ(G) = 2 in The-
orem 3.5. Since WTD(2) graphs have ρ(G) ≤ 2, in order to complete the characterization
of all WTD(2) graphs, it remains to answer the following question:
Problem 5.2. What are WTD(2) graphs with ρ(G) = 1?
Along the same line, one may consider to generalize our result in Theorem 3.5. It
is well known that ρ(G) ≤ γt(G) ≤ Γt(G); hence graphs with ρ(G) = Γt(G) form a
subclass of WTD graphs. This suggests our next open problem:
Problem 5.3. What are WTD(k) graphs with ρ(G) = k?
Lastly, we have shown in Theorem 3.15 that planar WTD(2) graphs with δ(G) ≥ 3
have at most 16 vertices. Our intuition is that 16 is not a tight bound. Thus, we pose the
following question:
Problem 5.4. Is the upper bound of 16 for the number of vertices of a planar WTD(2)
graph with δ(G) ≥ 3 tight? Can we determine all (finitely many) planar WTD(2) graphs?
S. Bahadır et al.: Well-totally-dominated graphs 221
ORCID iDs
Selim Bahadır https://orcid.org/0000-0003-1533-7194
Tınaz Ekim https://orcid.org/0000-0002-1171-9294
Didem Gözüpek https://orcid.org/0000-0001-8450-1897
References
[1] S. Bahadır and D. Gözüpek, On a class of graphs with large total domination number, Discrete
Math. Theor. Comput. Sci. 20 (2018), #23, doi:10.23638/dmtcs-20-1-23.
[2] E. Boros, V. Gurvich and P. L. Hammer, Dual subimplicants of positive boolean functions,
Optim. Methods Softw. 10 (1998), 147–156, doi:10.1080/10556789808805708.
[3] R. C. Brigham, J. R. Carrington and R. P. Vitray, Connected graphs with maximum total dom-
ination number, J. Combin. Math. Combin. Comput. 34 (2000), 81–96.
[4] E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, Total domination in graphs, Networks 10
(1980), 211–219, doi:10.1002/net.3230100304.
[5] T. Eiter and G. Gottlob, Identifying the minimal transversals of a hypergraph and related prob-
lems, SIAM J. Comput. 24 (1995), 1278–1304, doi:10.1137/s0097539793250299.
[6] Q. Fang, On the computational complexity of upper total domination, Discrete Appl. Math. 136
(2004), 13–22, doi:10.1016/s0166-218x(03)00195-1.
[7] A. Finbow, A. Frendrup and P. D. Vestergaard, Total well dominated trees, Research Report R-
2009-14, Department of Mathematical Sciences, Aalborg University, 2009, https://vbn.
aau.dk/en/publications/total-well-dominated-trees.
[8] A. Finbow, B. Hartnell and R. Nowakowski, Well-dominated graphs: a collection of well-
covered ones, Ars Combin. 25 (1988), 5–10.
[9] S. Finbow and C. M. van Bommel, Triangulations and equality in the domination chain, Dis-
crete Appl. Math. 194 (2015), 81–92, doi:10.1016/j.dam.2015.05.025.
[10] T. J. Gionet, E. L. C. King and Y. Sha, A revision and extension of results on 4-regular, 4-
connected, claw-free graphs, Discrete Appl. Math. 159 (2011), 1225–1230, doi:10.1016/j.dam.
2011.04.013.
[11] D. Gözüpek, A. Hujdurović and M. Milanič, Characterizations of minimal dominating sets and
the well-dominated property in lexicographic product graphs, Discrete Math. Theor. Comput.
Sci. 19 (2017), #25, doi:10.23638/dmtcs-19-1-25.
[12] B. Hartnell and D. F. Rall, On graphs in which every minimal total dominating set is minimum,
Congr. Numer. 123 (1997), 109–117, proceedings of the Twenty-eighth Southeastern Inter-
national Conference on Combinatorics, Graph Theory and Computing (Boca Raton, Florida,
1997).
[13] B. L. Hartnell, Well-covered graphs, J. Combin. Math. Combin. Comput. 29 (1999), 107–116.
[14] T. W. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs, volume
208 of Monographs and Textbooks in Pure and Applied Mathematics, CRC press, Boca Raton,
Florida, 1998, doi:10.1201/9781482246582.
[15] M. A. Henning and A. Yeo, Total Domination in Graphs, Springer Monographs in Mathemat-
ics, Springer, New York, 2013, doi:10.1007/978-1-4614-6525-6.
[16] X. Hou, Y. Lu and X. Xu, A characterization of (γt, 2γ)-block graphs, Util. Math. 82 (2010),
155–159.
[17] V. E. Levit and D. Tankus, Well-dominated graphs without cycles of lengths 4 and 5, Discrete
Math. 340 (2017), 1793–1801, doi:10.1016/j.disc.2017.02.021.
222 Ars Math. Contemp. 20 (2021) 209–222
[18] J. Pfaff, R. Laskar and S. T. Hedetniemi, Linear algorithms for independent domination and
total domination in series-parallel graphs, Congr. Numer. 45 (1984), 71–82, proceedings of the
Fifteenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Baton
Rouge, Louisiana, 1984).
[19] M. D. Plummer, Well-covered graphs: a survey, Quaestiones Math. 16 (1993), 253–287, doi:
10.1080/16073606.1993.9631737.
[20] J. Topp and L. Volkmann, Well covered and well dominated block graphs and unicyclic graphs,
Math. Pannon. 1 (1990), 55–66, http://mathematica-pannonica.ttk.pte.hu/
articles/mp01-2/mp01-2-055-066.pdf.