Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 89–97
A note on domination and
independence-domination numbers of graphs∗
Martin Milanič
University of Primorska, UP IAM, Muzejski trg 2, SI6000 Koper, Slovenia, and
University of Primorska, UP FAMNIT, Glagoljaška 8, SI6000 Koper, Slovenia
Received 30 November 2011, accepted 25 April 2012, published online 1 June 2012
Abstract
Vizing’s conjecture is true for graphs G satisfying γi(G) = γ(G), where γ(G) is
the domination number of a graph G and γi(G) is the independence-domination number
of G, that is, the maximum, over all independent sets I in G, of the minimum number of
vertices needed to dominate I . The equality γi(G) = γ(G) is known to hold for all chordal
graphs and for chordless cycles of length 0 (mod 3). We prove some results related to
graphs for which the above equality holds. More specifically, we show that the problems
of determining whether γi(G) = γ(G) = 2 and of verifying whether γi(G) ≥ 2 are NP-
complete, even if G is weakly chordal. We also initiate the study of the equality γi = γ in
the context of hereditary graph classes and exhibit two infinite families of graphs for which
γi < γ.
Keywords: Vizing’s conjecture, domination number, independence-domination number, weakly chor-
dal graph, NP-completeness, hereditary graph class, IDD-perfect graph.
Math. Subj. Class.: 05C69, 68Q17
1 Introduction
The closed neighborhood NG[v] of a vertex in a (finite, simple, undirected) graph G is the
set consisting of v itself and its neighbors in the graph. A set A of vertices is said to domi-
nate a set B if B ⊆ ∪{NG[a]: a ∈ A}. The minimum size of a set of vertices dominating
a set A is denoted by γG(A). A dominating set in a graph G is a set D of vertices that
dominates V (G). We write γ(G) for γG(V (G)). The concept of domination in graphs
has been extensively studied, both in structural and algorithmic graph theory, because of its
numerous applications to a variety of areas. Domination naturally arises in facility location
∗This work is supported in part by “Agencija za raziskovalno dejavnost Republike Slovenije”, research pro-
gram P1–0285 and research projects J1–4010, J1–4021 and N1–0011.
E-mail address: martin.milanic@upr.si (Martin Milanič)
Copyright c© 2013 DMFA Slovenije
90 Ars Math. Contemp. 6 (2013) 89–97
problems, in problems involving finding sets of representatives, in monitoring communi-
cation or electrical networks, and in land surveying. The two books [14, 15] discuss the
main results and applications of domination in graphs. Many variants of the basic concepts
of domination have appeared in the literature. Again, we refer to [14, 15] for a survey of
the area, and to [4, 10, 11, 13, 16, 18, 19, 21, 22] for some recent papers on domination and
variants thereof.
The Cartesian product of two graphs G and H is the graph GH with vertex set
V (G) × V (H) and edge set {(u, x)(v, y) : (u, x), (v, y) ∈ V (G) × V (H), u = v and
xy ∈ E(H), or x = y and uv ∈ E(G)}. In 1968 Vizing made the following conjecture,
according to Brešar et al. [8] “arguably the main open problem in the area of domination
theory”:
Conjecture 1. For every two graphs G and H , it holds that γ(GH) ≥ γ(G)γ(H).
The conjecture is still open and was verified for several specific classes of graphs; see,
e.g., [8].
An independent set in a graph is a set of pairwise non-adjacent vertices. The
independence-domination number γi(G) is the maximum of γG(I) over all independent
sets I in G. The independence-domination number has arisen in the context of matching
theory, see, e.g., [2, 20], and was first introduced in the context of domination by Aharoni
and Szabó in 2009 [3]. Obviously, γi(G) ≤ γ(G), and in general the gap between the two
may be large [3]. However, equality holds for:
• cycles of length 0 (mod 3), and more generally, for graphs that have a set of γ(G)
vertices with pairwise disjoint closed neighborhoods [17];
• chordal graphs, as proved by Aharoni, Berger and Ziv [1] in a result on width and
matching width of families of trees.
Recall that a graphG is called chordal if it does not contain any induced cycle of length
at least 4, and weakly chordal if it does not contain any induced cycles of length at least 5
or their complements.
Theorem 2 ( [1]). For every chordal graph G, it holds that γi(G) = γ(G).
The independence-domination number is related to Vizing’s conjecture via the follow-
ing result proved by Aharoni and Szabó [3]:
Theorem 3 ( [3]). For every two graphs G and H , it holds that γ(GH) ≥ γi(G)γ(H).
In particular, Vizing’s conjecture is true for chordal graphs. More generally, if G is a
graph with γi(G) = γ(G) then γ(GH) ≥ γ(G)γ(H) for every graph H . In a recent
survey paper on Vizing’s conjecture [8], Brešar et al. asked what other classes of graphs
can be found for which γi(G) = γ(G) for every G in the class.
In this note, we prove some results related to graphs for which the independence-
domination number coincides with the domination number. First, using a relationship be-
tween the independence-domination number and the notion of a dominating clique, we
prove that determining whether γi(G) = γ(G) is NP-hard. More specifically, we show
that it is NP-complete to determine whether γi(G) ≥ 2, as well as to determine whether
γi(G) = γ(G) = 2. These results, obtained in Section 2, remain valid for weakly chordal
graphs.
M. Milanič: A note on domination and independence-domination numbers of graphs 91
In Section 3, we turn our attention to graphs in which the equality γi = γ holds in
the hereditary sense. We show that this class, which properly contains the class of chordal
graphs, is properly contained in the class of graphs in which all induced cycles are of length
0 (mod 3). We do this by constructing an infinite family of graphs in which all induced
cycles are of length 0 (mod 3) but where the independence-domination number is strictly
smaller than the domination number. In conclusion, we propose three related problems.
2 The complexity of computing γi and testing γi = γ
In this section, we study some computational complexity aspects of computing the
indepedence-domination number and comparing it to the domination number. We first
recall some notions needed in our proofs. For a graph G = (V,E), we denote by G its
complement, that is, the graph with the same vertex set as G, in which two vertices are
adjacent if and only if they are not adjacent inG. A clique in a graph is a subset of pairwise
adjacent vertices. A dominating set that is also a clique is called a dominating clique. We
assume familiarity with basic notions of computational complexity (see, e.g., [12]).
Theorem 4. Given a weakly chordal graph G, it is NP-complete to determine whether
γi(G) ≥ 2.
Proof. To show membership in NP, observe that a short certificate for the fact that γi(G) ≥
2 is any independent set I such that for every vertex v ∈ V (G), it holds that I * NG[v].
To show hardness, we make a reduction from the problem of determining whether a
given weakly chordal graph contains a dominating clique. This is an NP-complete problem,
see, e.g., [6]. Clearly, the problem remains NP-complete if we assume that the input graph
G does not have a dominating vertex.
Suppose that we are given a weakly chordal graph G without dominating vertices. We
compute its complementary graph H = G. Since H is also weakly chordal, the theorem
follows immediately from the claim below.
Claim: G has a dominating clique if and only if γi(H) ≥ 2.
For the forward implication, suppose that G has a dominating clique K. We will show
that γi(H) ≥ 2 by showing that γH(K) ≥ 2. Suppose for a contradiction that γH(K) = 1.
Then, there exists a vertex v ∈ V (H) = V (G) such that K ⊆ NH [v]. In particular, v must
belong to K, since otherwise in G, vertex v would not have any neighbors in K, contrary
to the assumption that K is dominating in G. Since K is independent in H , that facts that
v ∈ K and K ⊆ NK [v] imply that K = {v}, that is, v is a dominating vertex in G, which
is impossible since we assumed that G has no dominating vertices. Hence, it holds that
γH(K) ≥ 2 and consequently γi(H) ≥ 2.
For the converse implication, suppose that γi(H) ≥ 2, and let I be an independent set
in H such that γH(I) ≥ 2. Clearly, I is a clique in G, and, in fact, a dominating clique: If
this were not the case, then there would exist a vertex v ∈ V (G) \ I such that in G, vertex
v is not adjacent to any vertex from I . Equivalently, for every u ∈ I , uv ∈ E(H). But then
{v} would dominate I in H , contrary to the assumption that γH(I) ≥ 2.
Corollary 5. Given a (weakly chordal) graphG and an integer k, it is NP-hard to determine
whether γi(G) ≥ k.
Corollary 6. Given a (weakly chordal) graphG and an integer k, it is NP-hard to determine
whether γi(G) ≤ k.
92 Ars Math. Contemp. 6 (2013) 89–97
How difficult it is to determine whether the values of γi and γ coincide? Since γi(G) ≤
γ(G) holds for every graph G, in order to show that
γi(G) = γ(G) = k , (2.1)
it suffices to argue that γi(G) ≥ k and γ(G) ≤ k. Clearly, for k = 1, whether (2.1) holds
can be determined in polynomial time: a necessary and sufficient condition for γi(G) =
γ(G) = 1 is that G has a dominating vertex.
We now show that already for k = 2, the problem becomes NP-complete, even for
weakly chordal graphs. The proof will also imply intractability of the problem of verifying
whether γi = γ.
Theorem 7. Given a weakly chordal graph G, it is NP-complete to determine whether
γi(G) = γ(G) = 2.
Proof. Membership in NP follows from the fact that a short certificate for γi(G) = γ(G) =
2 is given by a pair (I,D) where I is an independent set not dominated by any vertex (prov-
ing γi(G) ≥ 2) and D is a dominating set of size two (proving γ(G) ≤ 2).
To show hardness, we make a reduction from 3-SAT [12]. The reduction is an adap-
tation of the reduction by Brandstädt and Kratsch [6] used to prove that the dominating
clique problem is NP-complete for weakly chordal graphs.
Suppose that we are given an instance to 3-SAT, that is, a Boolean formula ϕ over
variables x1, . . . , xn, consisting of m clauses of length 3, say Ci = x
αi1
i1
∨ xαi2i2 ∨ x
αi3
i3
for
i = 1, . . . ,m, where αij ∈ {0, 1}, with the usual interpretation that x1i = xi and x0i = xi.
Without loss of generality, we may assume the following properties of the formula:
Property 1: No clause contains both a literal and its negation. (This is because clauses
containing both a literal and its negation can be discarded as they will always be satisfied.)
Property 2: There exist two clauses, sayC1 andC2, that have no literals in common. (If
the given formula ϕ does not have this property, we simply add to it a new clause consisting
of three new variables. If necessary, we relabel the clauses.)
Consider the graph H defined as follows:
V (H) = {x1, x1, . . . , xn, xn} ∪ {C1, . . . , Cm} ,
E(H) = {xα1i x
α2
j | 1 ≤ i, j ≤ n, i 6= j, α1, α2 ∈ {0, 1}}∪
{xαi Cj | 1 ≤ i ≤ n, 1 ≤ j ≤ m, α ∈ {0, 1}, xαi is a literal in Cj} .
We complete the reduction by computing the complementary graph G = H .
Using Property 1, it is easy to verify that neither H nor G contain an induced cycle
of length at least 5, that is, G is weakly chordal. Moreover, the following properties are
equivalent:
(i) ϕ is satisfiable.
(ii) H has a dominating clique.
(iii) γi(G) = γ(G) = 2.
(iv) γi(G) = γ(G).
The equivalence between (i) and (ii) has been established in [6].
(ii) implies (iii): Suppose thatH has a dominating clique. SinceH has no dominating
vertex, similar arguments as in the proof of Theorem 4 allow us to conclude that γi(G) ≥ 2.
Furthermore, by Property 1 and by construction ofH , vertices C1 and C2 have no common
M. Milanič: A note on domination and independence-domination numbers of graphs 93
neighbors in H . This implies that {C1, C2} is a dominating set in G. Therefore γ(G) ≤ 2,
and the conclusion follows since 2 ≤ γi(G) ≤ γ(G) ≤ 2.
Trivially, (iii) implies (iv).
(iv) implies (ii): Suppose that γi(G) = γ(G). Since H has no isolated vertices, G has
no dominating vertices. Therefore γi(G) = γ(G) ≥ 2, and it can be shown, similarly as in
the proof of Theorem 4, that H has a dominating clique.
This completes the proof.
Theorem 8. Given a weakly chordal graphG, it is NP-hard to determine whether γi(G) =
γ(G).
Proof. Perform the same reduction as in the proof of Theorem 7 and use the fact that the
formula is satisfiable if and only if γi(G) = γ(G).
3 A hereditary view on γi = γ
In this section, we initiate the study of the equality between the domination and
independence-domination number of graphs in the context of hereditary graph classes. A
graph class is said to be hereditary if it is closed under vertex deletions. The family of
hereditary graph classes is of particular interest, first of all, since many natural graph prop-
erties are hereditary, and second, since hereditary (and only hereditary) classes admit a
uniform description in terms of forbidden induced subgraphs. For a set F of graphs, we
say that a graph G is F-free if it does not contain an induced subgraph isomorphic to a
member of F . The set of all F-free graphs will be denoted by Free(F). Notice that for
two sets F1 and F2 of graphs, it holds that Free(F1 ∪ F2) = Free(F1) ∩ Free(F2).
Given a hereditary class G, denote by F the set of all graphs G with the property that
G 6∈ G but H ∈ G for every proper induced subgraph H of G. The set F is said to be
the set of (minimal) forbidden induced subgraphs for G, and G is precisely the class of
F-free graphs. The set F can be either finite or infinite, and many interesting classes of
graphs can be characterized as being F-free for some family F . Such characterizations
can be useful for establishing inclusion relations among hereditary graph classes, and were
obtained for numerous graph classes (see, e.g. [7]). The most famous such class is probably
the class of perfect graphs, for which the forbidden induced subgraph characterization is
given by the Strong Perfect Graph Theorem conjectured by Berge in 1961 [5] and proved
by Chudnovsky, Robertson, Seymour and Thomas in 2006 [9].
Since Vizing’s conjecture holds for graphs G such that γi(G) = γ(G), it would be
interesting to determine the largest hereditary class of graphs with this property. Moreover,
since recognizing graphs with γi = γ is NP-hard, it would also be interesting to determine
whether graphs in which the property γi = γ holds in the hereditary sense can be recog-
nized efficiently. With this motivation in mind, we introduce the class of independence-
domination-domination-perfect graphs, or shortly, IDD-perfect graphs, that is, graphs for
which the above equality holds in the hereditary sense:
IDD-perfect graphs = {G : γi(H) = γ(H) for every induced subgraph H of G} .
We now provide some partial results towards a characterization of IDD-perfect graphs.
By Theorem 2, we can immediately relate the class of IDD-perfect graphs to a well studied
hereditary subclass of perfect graphs, the class of chordal graphs:
94 Ars Math. Contemp. 6 (2013) 89–97
Theorem 9.
Chordal graphs ⊂ IDD-perfect graphs .
Proof. Since every induced subgraph of a chordal graph is chordal, Theorem 2 implies
that the class of IDD-perfect graphs contains the class of chordal graphs. This inclusion is
proper since chordless cycles of length congruent to 0 (mod 3) are IDD-perfect [17] (but
not chordal).
In the rest of this section, we bound the class of IDD-perfect graphs from above, by
exhibiting two infinite families of graphs that do not belong to class of IDD-perfect graphs:
the chordless cycles of length not congruent to 0 (mod 3) and another graph family, which
we describe now. For positive integers k1, k2, k3 > 1, let Fk1,k2,k3 denote the graph ob-
tained from the disjoint union of three cycles C1, C2 and C3 where |V (Cj)| = 3kj as
follows: denoting by (vj1, . . . , v
j
3kj
) a cyclic order of vertices of Cj , we identify vertex v21
with vertex v13k1 , vertex v
3
1 with vertex v
2
3k2
, and vertex v11 with vertex v
3
3k3
. See Fig. 1 for
an example.
v16
v26
v12 v
1
3
v14
v15
v22
v23v
2
4
v25
v32
v33
v34 v
3
5
C1C3
C2
v11
v21
v31
v36
Figure 1: The graph F2,2,2
Theorem 10.
IDD-perfect graphs ⊆ Free
( ⋃
k≥1
{
C3k+1, C3k+2
}
∪
⋃
k1,k2,k3>1
{
Fk1,k2,k3
})
.
Proof. First, we establish the inclusion IDD-perfect graphs ⊆
Free
(⋃
k≥1{C3k+1, C3k+2}
)
. To this end, we show that for every chordless cycle
C of order n = 3k + 1 or n = 3k + 2 (where k is a positive integer), it holds that
γi(C) = k and γ(C) = k + 1. Let (v1, . . . , vn) be a cyclic order of the vertices of such a
cycle C. Observe that for every set S ⊆ V (C) with |S| ≤ k, it holds that
| ∪v∈S NC(v)| ≤
∑
v∈S
|NC [v]| = 3|S| < n .
Thus, we immediately have γ(C) ≥ k + 1. On the other hand, the set
{v3j−2 : 1 ≤ j ≤ k + 1}
M. Milanič: A note on domination and independence-domination numbers of graphs 95
is dominating, proving γ(C) = k + 1. Suppose now that I is an independent set in C.
We may assume w.l.og. that v1 6∈ I . In case that n = 3k + 2, we may also assume that
vn 6∈ I . In either case, the set {v3j : 1 ≤ j ≤ k} is a set of size k dominating I . This
shows that γi(C) ≤ k. Conversely, since the set I = {v3j : 1 ≤ j ≤ k} is a set of k
vertices with pairwise disjoint closed neighborhoods, we have γi(C) ≥ γC(I) = |I| = k.
Thus k = γi(C) < γ(C) = k + 1 and hence no IDD-perfect graph can contain C as an
induced subgraph.
It remains to show that IDD-perfect graphs ⊆ Free
(⋃
k1,k2,k3>1
{Fk1,k2,k3}
)
. Equiv-
alently, we must show that for every three integers k1, k2, k3 > 1, it holds that
γi(Fk1,k2,k3) < γ(Fk1,k2,k3). We will show this in two steps, by computing the exact
values of γi(Fk1,k2,k3) and γ(Fk1,k2,k3).
Let F = Fk1,k2,k3 for some k1, k2, k3 > 1. First, we show that γ(F ) = k1+k2+k3−1.
Consider the set
D = {v13j−2 : 1 ≤ j ≤ k1} ∪ {v23j−1 : 1 ≤ j ≤ k2} ∪ {v33j : 1 ≤ j ≤ k3 − 1} .
Then,D is a dominating set of size k1+k2+k3−1, showing that γ(F ) ≤ k1+k2+k3−1 .
Now, we show that γ(F ) ≥ k1 + k2 + k3 − 1 . Suppose for a contradiction that D is a
dominating set in F with |D| ≤ k1+k2+k3− 2. Clearly, for every p ∈ {1, 2, 3}, we have
that |D ∩ V (Cp)| ≥ kp. Moreover, D must contain at least kp − 1 vertices from Cp other
than vp1 and v
p
3kp
since otherwise not all vertices in the set {v13p−2 : 2 ≤ j ≤ kp} can be
dominated by D. This implies that |D ∩ {v11 , v21 , v31}| = 1. We may assume without loss
of generality that D ∩ {v11 , v21 , v31} = {v11}. But this implies that |D ∩ V (C2)| = k2 − 1, a
contradiction. Hence γ(F ) = k1 + k2 + k3 − 1.
In the rest of the proof, we show that γi(F ) = k1 + k2 + k3 − 2 . Consider the set
I = {v13j : 1 ≤ j ≤ k1} ∪ {v23j−2 : 1 ≤ j ≤ k2} ∪ {v33j : 1 ≤ j ≤ k3 − 1} .
This is is a set of k1 + k2 + k3 − 2 vertices with pairwise disjoint closed neighborhoods.
Therefore γi(F ) ≥ |I| = k1+k2+k3−2 . To see that γi(F ) ≤ k1+k2+k3−2 , we will
verify that γF (I) ≤ k1 + k2 + k3 − 2 for every independent set I in F . Up to symmetry, it
is sufficient to consider the following two cases:
• Case 1: v12 6∈ I .
In this case, the set
D = {v13j−2 : 2 ≤ j ≤ k1} ∪ {v23j : 1 ≤ j ≤ k2} ∪ {v33j−2 : 2 ≤ j ≤ k3}
is a set of size k1 + k2 + k3 − 2 dominating I .
• Case 2: {v12 , v13k1−1, v
2
2 , v
2
3k2−1, v
3
2 , v
3
3k3−1} ⊆ I .
In this case, the set
D = {v11 , v21 , v31} ∪ {v13j−1 : 2 ≤ j ≤ k1 − 1} ∪ {v23j−1 : 2 ≤ j ≤ k2 − 1}∪
{v33j−1 : 2 ≤ j ≤ k3 − 1}
is a set of size k1 + k2 + k3 − 3 dominating I .
This shows that k1 + k2 + k3 − 2 = γi(F ) < γ(F ) = k1 + k2 + k3 − 1 and hence no
IDD-perfect graph in can contain F = Fk1,k2,k3 as an induced subgraph.
This completes the proof.
96 Ars Math. Contemp. 6 (2013) 89–97
Remark. Theorem 10 shows that the class of IDD-perfect graphs is not comparable with
the class of perfect graphs. On the one hand, the 9-cycle is an IDD-perfect graph that is
not perfect. On the other hand, the 4-cycle is a (bipartite, hence) perfect graph that is not
IDD-perfect.
4 Conclusion
We conclude this note with three problems related to results from Section 3.
Problem 1. Determine whether every graph of the form Fk1,k2,k3 is a minimal forbidden
induced subgraph for the class of IDD-perfect graphs.
Problem 2. Determine the set of minimal forbidden induced subgraphs for the class of
IDD-perfect graphs.
Problem 3. Determine the computational complexity of recognizing IDD-perfect graphs.
Acknowledgements
The author would like to thank Douglas Rall for stimulating discussions, and the three
anonymous referees for comments that helped to improve the presentation of the paper.
In addition, one referee suggested a significant simplification of a part of the proof of
Theorem 10.
References
[1] R. Aharoni, E. Berger and R. Ziv, A tree version of König’s theorem, Combinatorica 22 (2002),
335–343.
[2] R. Aharoni and P. Haxell, Hall’s theorem for hypergraphs, J. Graph Theory 35 (2000), 83–88.
[3] R. Aharoni and T. Szabó, Vizing’s conjecture for chordal graphs, Discrete Math. 309 (2009),
1766–1768.
[4] G. Bacsó, Complete description of forbidden subgraphs in the structural domination problem,
Discrete Math. 309 (2009), 2466–2472.
[5] C. Berge, Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss.
Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114.
[6] A. Brandstädt and D. Kratsch, On domination problems for permutation and other graphs,
Theoret. Comp. Sci. 54 (1987), 181–198.
[7] A. Brandstädt, V. B. Le and J. Spinrad, Graph classes: a survey. SIAM Monographs on Discrete
Mathematics and Applications. SIAM, Philadelphia, PA, 1999.
[8] B. Brešar, P. Dorbec, W. Goddard, B. L. Hartnell, M. A. Henning, S. Klavžar, D. F. Rall,
Vizing’s conjecture: a survey and recent results, J. Graph Theory 69 (2012), 46–76.
[9] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect graph theorem,
Ann. of Math. 164 (2006), 51–229.
[10] F. Dahme, D. Rautenbach and L. Volkmann, Some remarks on α-domination, Discuss. Math.
Graph Theory 24 (2004), 423–430.
[11] J. E. Dunbar, D. G. Hoffman, R. C. Laskar and L. R. Markus, α-Domination, Discrete Math.
211 (2000), 11–26.
M. Milanič: A note on domination and independence-domination numbers of graphs 97
[12] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-
Completeness, W. H. Freeman, 1979.
[13] F. Harary and T. W. Haynes, Double domination in graphs, Ars Combin. 55 (2000), 201–213.
[14] T. W. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs, Marcel
Dekker, 1998.
[15] T. W. Haynes, S. Hedetniemi and P. Slater (Eds.), Domination in Graphs: Advanced Topics,
Marcel Dekker, 1998.
[16] M. A. Henning and A. P. Kazemi, k-tuple total domination in graphs, Discrete Appl. Math.
158 (2010), 1006–1011.
[17] M. S. Jacobson and L. F. Kinch, On the domination of the products of graphs. II. Trees, J.
Graph Theory 10 (1986), 97–106.
[18] R. Klasing and C. Laforest, Hardness results and approximation algorithms of k-tuple domi-
nation in graphs, Inform. Process. Lett. 89 (2004), 75–83.
[19] H. Liu, M.J. Pelsmajer, Dominating sets in triangulations on surfaces, Ars Math. Contemp. 4
(2011), 177–204.
[20] R. Meshulam, The clique complex and hypergraph matching, Combinatorica 21 (2001), 89–94.
[21] O. Schaudt, On the existence of total dominating subgraphs with a prescribed additive heredi-
tary property, Discrete Math. 311 (2011), 2095–2101.
[22] Zs. Tuza, Hereditary domination in graphs: Characterization with forbidden induced sub-
graphs, SIAM J. Discrete Math. 22 (2008), 849–853.