![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
Imagine that we are given a set of officials and a set
of civils. For each civil
, there must be an official
that can serve
, and whenever any such
is serving
, there must also be another civil
that observes
, that is,
may act as a kind of witness, to avoid any abuse from
. What is the minimum number of officials to guarantee such a service, assuming a given social network?
In this paper, we introduce the concept of certified domination that models the aforementioned problem. Specifically, a dominating set of a graph
is said to be certified if every vertex in
has either zero or at least two neighbours in
. The cardinality of a minimum certified dominating set in
is called the certified domination number of
. Herein, we present the exact values of the certified domination number for some classes of graphs as well as provide some upper bounds on this parameter for arbitrary graphs. We then characterise a wide class of graphs with equal domination and certified domination numbers and characterise graphs with large values of certified domination numbers. Next, we examine the effects on the certified domination number when the graph is modified by deleting/adding an edge or a vertex. We also provide Nordhaus–Gaddum type inequalities for the certified domination number.
1 Introduction
Imagine that we are given a set of officials and a set
of civils. For each civil
, there must be an official
that can serve
, and whenever any such
is serving
, there must also be another civil
that observes
, that is,
may act as a kind of witness, to avoid any abuse from
. What is the minimum number of officials to guarantee such a service, assuming a given social network? This problem motivates us introducing the concept of certified domination. Specifically, let
be a subset of the vertex set of a graph
. We say that
dominates
(or is a dominating set of
) if each vertex in the set
has a neighbour in
. The cardinality of a minimum dominating set in
is called the domination number of
and denoted by
, and any minimum dominating set of
is called a
-set. A dominating set
of
is called certified if every vertex
has either zero or at least two neighbours in
. The cardinality of a minimum certified dominating set in
is called the certified domination number of
and denoted by
. A minimum certified dominating set of
is called a
-set. Notice that, by the definition,
is a certified dominating set of
, and certainly
. Furthermore, one can observe that
.
There is a wealth of literature about domination and its variations in graphs; we refer to the excellent books of Haynes, Hedetniemi, and Slater [Citation1,2]. The domination concept we introduce perfectly fits into that area where, for a given graph , domination parameters are defined by imposing additional constraints on a dominating set
or its complement
. This area includes, to mention but a few, multiple domination, distance domination, or global domination. In particular, the problem of certified domination is closely related to the problem of existence a
-pair in a graph, introduced by Henning and Rall in [Citation3]. Recall, a set
of vertices is
-dominating in
if every vertex in
has at least two neighbours in
. A
-pair of
is a pair
of disjoint sets of vertices of
such that
is a dominating set of
and
is a
-dominating set of
; a graph that has a
-pair is called a
-graph. One can observe that if
has a
-pair
, then the set
is a certified dominating set. However, there are graphs
with
for any
-pair in
(if any), see for an illustration.
Fig. 1 The family of graphs . (a) Black vertices form a certified dominating set
with
,
. (b) Black and grey vertices form a
-pair, respectively, with
. Observe that if
, then
has no
-pair with
.
![Fig. 1 The family of graphs Gi. (a) Black vertices form a certified dominating set Dc with |Dc|=i+3, i≥2. (b) Black and grey vertices form a (D,D2)-pair, respectively, with |D|=2i+1. Observe that if i≥3, then Gi has no (D,D2)-pair with |D|≤i+3.](/cms/asset/803bca95-d73d-4f0f-bb13-380c1f7b3b0c/uakc_a_1758484_f0001_b.jpg)
In Section 2, we present the exact values of the certified domination number for some elementary classes of graphs. Some upper bounds on this new parameter for an arbitrary graph are presented in Section 3. Then, in Sections 4 and 5, respectively, we characterise a wide class of graphs with equal domination and certified domination numbers and characterise graphs with large values of certified domination numbers. Next, in Section 6, we examine the effects on the certified domination number when the graph is modified by deleting/adding an edge or a vertex. Finally, Section 7 is devoted to Nordhaus–Gaddum type inequalities for the certified domination number.
1.1 Definitions and notation
For general graph theory terminology, we follow [Citation4]. In particular, for a vertex of a graph
, its neighbourhood, denoted by
, is the set of all vertices adjacent to
, and the cardinality of
, denoted by
, is called the degree of
. The closed neighbourhood of
, denoted by
, is the set
. In general, for a subset
of vertices, the neighbourhood of
, denoted by
, is defined to be
, and the closed neighbourhood of
, denoted by
, is the set
. The minimum (maximum, resp.) degree of a vertex in
is denoted by
(
, resp.). A vertex of degree
is called a universal vertex of
. A vertex of degree one is called a leaf, and the only neighbour of a leaf is called its support vertex (or simply, its support). If a support vertex has at least two leaves as neighbours, we call it a strong support, otherwise it is a weak support. The set of leaves of
is denoted by
. For a leaf
, its support vertex is denoted by
, and for a weak support
, the unique leaf adjacent to
is denoted by
. The set of weak supports of
is denoted by
, while the set of strong supports of
is denoted by
.
2 Elementary graph classes
We begin by presenting the exact values of the certified domination number for some elementary classes of graphs.
Observation 2.1
If is an
-vertex path, then
Observation 2.2
If is an
-vertex cycle,
, then
.
Observation 2.3
If is an
-vertex complete graph, then
Observation 2.4
If is a complete bipartite graph with
, then
Observation 2.5
If is an
-vertex wheel, then
.
In addition, we have the following two general observations on the certified domination number of a graph.
Observation 2.6
If is a graph of order at least three, then
if and only if
has a universal vertex.
Observation 2.7
If are the connected components of a graph
, then
.
3 Upper bounds on the certified domination number
In this section we focus on upper bounds on the certified domination number. We start with two simple observations and then present our main result of this section: an upper bound on with respect to the domination number
and the number
of weak supports in
.
Observation 3.1
Every support vertex of a graph belongs to every certified dominating set of
.
Proof
Let be a certified dominating set of
, let
be a support vertex of
, and let
be a leaf adjacent to
. If
were not in
, then
should be in
. But then
would have only one neighbour in
, and
would not be a certified dominating set. □
Observation 3.2
Let be a graph of order
. If the strong supports of
are adjacent to
leaves in total, then
. In particular,
.
Proof
Let be the set of all leaf-neighbours of strong supports of
. Then
and the set
is a certified dominating set of
. Thus
as
. □
Before we present our main result, let us introduce some useful terminology. Let be a dominating set of a graph
. An element of
that has all neighbours in
is said to be shadowed with respect to
(shadowed for short), an element of
that has exactly one neighbour in
is said to be half-shadowed with respect to
(half-shadowed for short), while an element of
having at least two neighbours in
is said to be illuminated with respect to
(illuminated for short). It is easy to observe that if
is a minimum dominating set of a graph with no isolated vertices, then
has no shadowed element, and if
is a certified dominating set, then
has no half-shadowed element.
Theorem 3.3
If is a connected graph, then
.
Proof
If is a graph of order at most two, then the inequality is obvious. Thus assume that
has at least three vertices. Let
be a
-set of
that minimises the number of half-shadowed vertices and such that
does not contain any leaf of
. (Notice that such
always exists as
is connected and
.) Let
be the set of all half-shadowed vertices of
. If
, then
. Thus assume that
.
Claim 1
If , then
and
.
The inequality follows from the choice of
, that is, from the assumption that
. To argue the second property, suppose on the contrary that
is a strong support. Again, since
has at least two neighbours in
and
,
would not be half-shadowed, a contradiction.
Next we show that all half-shadowed vertices are weak supports. Suppose on the contrary that there is a half-shadowed vertex and let
be the unique neighbour of
in
. Since
is neither a weak nor strong support (by assumption and Claim 1, respectively), it implies that
is not a leaf. Furthermore, we have the following claim.
Claim 2
The set is a subset of
.
Otherwise the set would be a smaller (than
) dominating set of
.
Finally, we have the following claim.
Claim 3
No vertex belonging to the set is shadowed.
If a vertex was shadowed, then the set
would be a smaller (than
) dominating set of
.
Consequently, keeping in mind the fact that none of neighbours of is a leaf (see Claim 1), and combining Claims 2 and 3, we conclude that the set
would be a
-set of
with a smaller number of half-shadowed vertices, a contradiction. This proves that the set
of half-shadowed vertices consists of weak supports of
only.
Observe now that adding to all leaves adjacent to half-shadowed weak supports results in a dominating set
of
with no half-shadowed vertices, that is,
is a certified dominating set of
. Therefore
. □
From Observation 2.7 and Theorem 3.3, we immediately obtain the following corollary.
Corollary 3.4
If is a graph, then
.
4 Graphs with ![](//:0)
![](//:0)
We continue our study on the certified domination number by focusing now on the class of graphs with . When trying to characterise this class, one may expect that the main problem lies in leaves of a graph. In fact, from Corollary 3.4 we immediately have the first result.
Corollary 4.1
If is a graph with no weak support, then
.
The above corollary also follows from the next more general lemma.
Lemma 4.2
If a connected graph has at least three vertices, then
if and only if there exists a minimum dominating set
of
such that
for every
.
Proof
Assume first that . Let
be a minimum certified dominating set of
. Then
is a minimum dominating set of
. Now, if
, then
(as
is dominating in
),
(otherwise
would be a smaller dominating set of
), and
(otherwise
would be half-shadowed). Thus
and
(otherwise
would be half-shadowed), and so
.
Assume now that in there exists a
-set
such that
for every
. Of all such sets, choose one, say
, that does not contain any leaf of
(such
exists in every connected graph of order at least three) and minimises the number of its half-shadowed vertices. We claim that such
is a certified dominating set of
(and therefore
). Suppose, on the contrary, that some element
of
is half-shadowed. Let
be the unique element of
. Since
is half-shadowed,
, and
(as every element of
is illuminated by the adjacent leaf and, by the assumption, by at least one non-leaf). Finally, since
(by the choice of
) and
, we have
and
. Now, if it were
, then
would be a dominating set of
smaller than
, a contradiction. Thus
must be a nonempty subset of
and, then,
is a minimum dominating set of
and it has less half-shadowed vertices than
, a final contradiction which proves that
. □
Observe that if , then
. Next, if
, then
. In the latter case,
and
has no minimum dominating set
of
such that
for every
. Therefore, taking into account Observation 2.7 and Lemma 4.2, we obtain the following corollary for graphs which are not necessarily connected.
Corollary 4.3
If is a graph, then
if and only if there exists a minimum dominating set
in
such that
for every
.
Furthermore, we have the following relation between graphs each of which has a unique minimum dominating set and those for which and
are equal.
Corollary 4.4
If a graph has a unique minimum dominating set, then
.
Proof
If , then
by Corollary 4.1. Thus assume that
. Let
be the minimum dominating set of
. From the uniqueness and minimality of
it follows that
and
. Now, if it were
, then, by Lemma 4.2, we could find
such that
, and then the set
would be another minimum dominating set of
, which is impossible. □
Remarks
From Corollary 4.1 and the fact that the problem of determining the domination number in bipartite planar subcubic graphs with no leaves is NP-hard (as it was observed in [Citation5,6]), we immediately obtain the following: The problem of determining the certified domination number is NP-hard even in bipartite planar subcubic graphs with no leaves. Next, let be a graph with no isolated vertex. If
has a minimal dominating set
which is also a certified dominating set, then its complement
is a
-dominating set of
, and, therefore,
is a
-graph. Thus, from Corollaries 4.1 and 4.4, we have the following generalisation of Theorem 3 in [Citation3]: Let
be a graph with no isolated vertex. If
has no weak support or
has a unique dominating set, then
is a
-graph and it has a
-pair in which
.
5 Graphs with large values of ![](//:0)
![](//:0)
As we have already observed, for any graph of order
,
,
, and there are graphs
with
, for example, the complement of a complete graph
or a 4-vertex path
. Thus it is natural to try to characterise all graphs with
and
, respectively, which is carried out in this section. In particular, we prove that
if and only if
is the complement of a complete graph, the corona of a graph, or the union of both of them. Recall, the corona product (or simply, the corona) of two graphs
and
is the graph
resulting from the disjoint union of
and
copies of
in which the
th vertex of
is joined to all vertices of the
th copy of
. If
is a 1-vertex graph,
, then the corona
is simply called the corona of
.
Lemma 5.1
Let be a connected graph of order
. If
is the corona of some graph, then
.
Proof
Let be a smallest certified dominating set of
. It suffices to prove that
. This is obvious if
. Thus assume
. In this case, since
is the corona of some graph, every vertex of
either is a leaf of
or is adjacent to exactly one leaf of
. From this and from Observation 3.1 it follows that
. Moreover, every leaf
of
also belongs to
(as otherwise its only neighbour
would be half-shadowed). Consequently,
and therefore
. □
Lemma 5.2
Let be a connected graph of order
. If
, then
is the corona of some graph.
Proof
The statement is obvious for connected graphs of order at most . Thus assume that
is a connected graph of order
and
. Now, since
for every graph with no isolated vertex, so by Theorem 3.3 we have
. Thus
and so
is the corona of some graph (as it was proved in [Citation7,8]). □
From the above lemmas, we immediately conclude with the following theorem.
Theorem 5.3
If is a graph of order
, then
if and only if
is either the complement of a complete graph, or the corona of a graph, or the union of both of them.
Remark
We incidentally observe that the above result implies the sharpness of the upper bound in the inequality (see Theorem 3.3 and Corollary 3.4) as well as in the inequality
, since for the corona
of any graph without an isolated vertex, we have
and
.
5.1 Graphs with ![](//:0)
![](//:0)
A diadem graph of a graph is a graph obtained from the corona
by adding a new vertex, say
, and joining
to one of support vertices of
(see ).
Lemma 5.4
If is a diadem graph of order
, then
.
Proof
Let be the unique strong support of
, and let
be the two leaves of
adjacent to
in
. It is obvious that
is a certified dominating set of
. Let
be a smallest certified dominating set of
. Then
(by Observation 3.1) and
. Moreover, every leaf
different from
and
belongs to
(otherwise
would be half-shadowed). Consequently
and therefore
. □
Lemma 5.5
Let be a connected graph of order
. If
, then
,
, or
is a diadem graph ( of a connected graph).
Proof
If is a connected graph of order at most
and
, then
,
or
. Thus assume that
. In this case
, as otherwise, since
(by Corollary 4.1),
, and
, we would have
, which is impossible. We now claim that
is a diadem graph.
By way of contradiction, suppose that the claim is false. Let be a smallest counterexample, say of order
(
), such that
and
is not a diadem graph. Let
be a
-set of
, and let
and
be the only elements of
. From the fact that
is a certified dominating set of
it follows that if
, then either
or
. This proves that
. In addition, the set
is nonempty, as otherwise
would be a certified dominating set of
and we would have
, which is impossible.
Let denote the subgraph
of
. From the assumption
it easily follows that
. Thus, by Theorem 5.3, every connected component of
is an isolated vertex or the corona of a graph.
Let be a connected component of
. From the fact that
is a minimum certified dominating set of
it follows that at least one vertex of
is not adjacent to any vertex belonging to
as otherwise
would be a certified dominating set of
, which is impossible as
. From this we conclude that
has no isolated vertex. Consequently, every connected component of
is the corona of a graph.
We now claim that is not a connected component of
. Suppose on the contrary that
on vertices
and
is a connected component of
. Then one of the vertices
and
is a leaf in
and the latter one is adjacent to a vertex in
, say
and
is adjacent to a vertex
. Let
denote the graph
(of order
). For this graph either
, or
, or
. Assume first that
. Let
be a smallest certified dominating set of
. Then
(if
) or
(if
) is a certified dominating set of
and
, a contradiction. Assume now that
. Then
and, by Theorem 5.3,
is the corona of a graph. But this is impossible as no vertex of
is a leaf or a neighbour of exactly one leaf. Finally, assume that
. In this case the choice of
implies that
is the diadem graph in which
and
are leaves and
is their only common neighbour. Now, it is obvious that the graph
(obtained from
by the addition of the vertices
and
, and the edges
and
) is a diadem graph, a contradiction.
Now, to complete the proof, it suffices to show that this smallest counterexample is not a counterexample, that is, it suffices to show that is a diadem graph. It is enough to prove that: (1) no vertex belonging to
is adjacent to a leaf of a connected component of
of order at least four, (2)
and
have exactly one common neighbour, and (3)
and
are not adjacent in
.
(1) | Suppose on the contrary that there is a vertex in | ||||
(2) | Suppose on the contrary that | ||||
(3) | Suppose on the contrary that |
From Theorem 5.3, Lemmas 5.4 and 5.5, we have the final characterisation of graphs of order with
.
Theorem 5.6
Let be a graph of order
. Then
if and only if
is
, or a diadem graph, or
is one of these three graphs with possible number of isolated vertices, or
is the union of one of these three graphs with the corona of some graph, with possible number of isolated vertices. □
6 Influence of deleting/adding edge/vertex
In this section, following [Citation9–12], to mention but a recent few, we examine the effects on the certified domination number when the graph is modified by deleting/adding an edge or a vertex. We observe that deleting an edge or a vertex may arbitrarily increase the certified domination number. For example, for the graph of order
illustrated in (a) we have
and
. To argue a similar influence of deleting a vertex, consider a wheel graph
with the hub
. We have
and
.
Adding an edge to a graph may also arbitrarily increase the certified domination number. Namely, consider the disconnected graph of order
illustrated in (b). We have
and
. However, adding an edge to a connected graph does not increase the certified domination number, that is,
for any connected graph
. To argue this property, we use the following lemma.
Lemma 6.1
Let be a
-set of a connected graph
of order
. Then:
(a) | Every shadowed vertex in | ||||
(b) | Every non-leaf neighbour of a shadowed weak support is either an illuminated vertex or a shadowed weak support. |
Proof
(a) Consider a shadowed vertex . Suppose on the contrary that
is neither a weak support nor a leaf in
. By minimality of
, there are no shadowed strong supports in
, in particular,
is not a strong support, and thus all neighbours of
are of degree at least two. Let
be a maximal subset of shadowed vertices such that (i)
, (ii) the induced subgraph
is connected, and (iii) none of elements of
is an illuminated vertex or a shadowed weak support. Next, for a vertex
, define the set
. Analogously, define the set
.
Observe that by minimality of , each vertex
is a non-support vertex, and by the choice of
, and every element in
is either an illuminated vertex or a shadowed weak support.
Case :
is a
-vertex graph. Let
be the set of shadowed leaves within the distance
from
. Then the set
would be a certified dominating set of
and
, a contradiction.
Case :
and
. By Theorem 5.3,
is the corona of some connected graph. Observe that by the choice of
and minimality of
, if
is a leaf of
, then the set
is non-empty.
Consider now a weak support in
. Let
be the set of leaves of
within the distance at most
from
and let
be the set of shadowed leaves of
within the distance
from
. Then the set
is a certified dominating set of
and
, a contradiction.
Case :
and
(as the case
is impossible). Let
be a
-set of
and let
. Let
be the set of shadowed leaves within the distance
from
. Then the set
is a certified dominating set of
and
, a contradiction.
(b) A non-leaf neighbour of a shadowed weak support is either illuminated or shadowed. If
is shadowed, then, since it is not a leaf, it must be a weak support by (a). □
Theorem 6.2
If is a connected graph of order
, then
.
Proof
One can verify the validity of the theorem for graphs of order at most . So assume
and let
be a
-set of
.
Let ,
, be the added edge to
. If both
, then
is also a certified dominating set of the graph
. Similarly, if either both
, or
and
is illuminated, or
is illuminated and
, then
is a certified dominating set of
as well. Therefore, in all aforementioned cases, we have
as required.
Without loss of generality assume now that and
is shadowed (the case
and
is shadowed can be analysed in a similar way). By Lemma 6.1
,
is either a weak support or a leaf of
.
Case :
is a weak support of
. Then the set
is a certified dominating set of
, and thus,
.
Case :
is a leaf of
. By the choice of
, it follows that the support vertex
is weak and shadowed. Therefore, by Lemma 6.1
, every non-leaf neighbour of the weak support
in
is either an illuminated vertex or a shadowed weak support of
. Let
be the set of shadowed leaves within the distance
from
in
. Then, the set
is a certified dominating set in
, and hence
. □
Adding a vertex can arbitrarily increase the certified domination number, which is not the case as in the model of classic domination. Indeed, for the graph of order
depicted in , we have
, while
. However, bearing in mind Corollary 4.1, one can expect that the clue of the above construction lies in adding a leaf. Indeed, this is the case since one can prove that adding a non-leaf vertex does not effect the certified domination number significantly (the being added vertex
is called a non-leaf vertex if
is not a leaf in the resulting graph). Namely, we have the following theorem.
Theorem 6.3
If we add a non-leaf vertex to a graph
, then
.
Proof
Let be a
-set of a graph
and let
be a new added vertex.
Case :
. Let
and
be the two neighbours of
in
. If either
or both
, then the set
is a certified dominating set of
, and thus
. Otherwise, without loss of generality, we consider two subcases.
Subcase .a:
,
, and
is illuminated. Then the set
remains a certified dominating set of
, and in this case,
holds.
Subcase .b:
,
, and
is shadowed. If the vertex
constitutes a
-vertex component of
, then the set
is a certified dominating set in
, thus getting
. Otherwise, by Lemma 6.1
,
is either a weak support or a leaf of
. Now, similarly as in the proof of Theorem 6.2, we consider two subcases.
Subcase .b.
:
is a weak support of
. (We emphasise that this subcase includes the case when
and the
constitute a
-vertex component of
.) Then the set
is a certified dominating set in
. In this case,
holds.
Subcase .b.
:
is a leaf of
, and
together with the support vertex
does not constitute a
-vertex component of
. By the choice of
, the support vertex
is weak and shadowed. By Lemma 6.1
, every non-leaf neighbour of
in
is either an illuminated vertex or a shadowed weak support of
. Again, let
be the set of shadowed leaves within the distance
from
in
. Then, the set
is a certified dominating set in
. In this case,
.
Case :
. Then, when adding
to
, we first add only two edges, thus obtaining a temporary graph
, where
. Now, taking into account Case 1, we conclude that
. Next, when adding all the remaining edges to
, sequentially, to obtain the final graph
, we apply Theorem 6.2, sequentially, for each of added edge, thus getting
as required. □
7 Nordhaus–Gaddum type results
Following the precursory paper of Nordhaus and Gaddum [Citation13], the literature has became abundant in inequalities of a similar type for many graph invariants, see a recent survey by Aouchiche and Hansen [Citation14]. In particular, the following result is known for the domination number.
Theorem 7.1
[15–17] If is the complement of a graph
of order
, then:
(a) |
| ||||
(b) |
|
Further sharpening of bounds was done for the case when, for example, both and
are connected [Citation18] or for graphs with specified minimum degree [Citation19], to mention but a few. In particular, the following theorem was proved in [Citation20].
Theorem 7.2
[Citation20] If is a graph of order
and neither
nor
has an isolated vertex, that is,
, then
Moreover, if
, the bound is attained if and only if
.
In this section we provide some Nordhaus–Gaddumtype inequalities for the certified domination number. First, taking into account Corollary 4.1, Theorems 7.1 and 7.2, we obtain the following corollary.
Corollary 7.3
If is a graph of order
and
, then
By enumerating all graphs of order at most , we obtain the following observation.
Observation 7.4
Let be a graph of order
. Then:
(a) |
| ||||
(b) |
| ||||
(c) |
|
Next, we have the following theorem.
Theorem 7.5
If is a graph of order
and
, then
In addition, if
, then each of the above upper bounds is attainable, and the following statements are equivalent:
(a) |
| ||||
(b) |
| ||||
(c) |
|
Proof
From the assumption , it follows that
and, therefore,
or
. Now, since
and
, we get
and
.
Assume now that , say
. Then
, and so
. Now, since
, it follows from each of the equalities
and
that
. Finally, since
and
, we conclude from Theorem 5.3 that
is the complement of
or the union of the corona of some graph and a positive number of isolated vertices. This proves the implications
and
. Opposite implications are straightforward. □
Finally, we have the following theorem.
Theorem 7.6
If is a graph of order
, then
In addition, each of the above upper bounds is attainable, and the following statements are equivalent:
(a) |
| ||||
(b) |
| ||||
(c) |
|
Proof
If , then
and
by Corollary 7.3. If
, then
and
by Theorem 7.5.
Thus assume . Then
. This also implies that
and
. Thus, since
and
, it suffices to show that
or
. Without loss of generality assume that
. Let
be a leaf of
and let
be the only element of
. We consider two cases:
, and
.
Case 1: . Let
be the only element of
. Assume first that
. Let
and
be two neighbours of
(and
). Now, because
,
,
, and
, we conclude that
is a minimum certified dominating set of
, and
. Assume now that
. In this case, let
and
be vertices such that
and
. Since
, the set
is dominating in
. In addition, since
and
, the set
is certified dominating in
. From this and from the fact that
it follows that
.
Case 2: . Let
and
be two elements of the set
. In this case,
is a certified dominating set of
, since
,
, and
. From this it again follows that
.
We now prove the equivalence of (a), (b), and (c). Let be a graph of order
such that
(
, respectively). From this assumption, from Corollary 7.3 and Theorem 7.5 it follows that
. Then, as we have already proved,
or
, and therefore
or
, respectively. From this and from Theorem 5.3 it follows that
or
is the corona of some graph. Thus, we have proved the implications
and
. Finally, assume that
is the corona of some graph and
is of order
. Then
by Theorem 5.3. From the fact that the corona has no isolated vertex, it follows that
. Now, since
, as in Case 2, we get
. Consequently,
and
. This proves the implications
and
. □
8 Concluding remarks
Since over the years researchers have published thousands of papers on the topic of domination in graphs, our paper cannot claim the right to cover the new model even partially, it should only be thought of as a very beginning, a small contribution to. In this section, we present three exemplary open problems that we find interesting and which research on we feel worth of being continued.
It is natural to characterise the class of critical graphs where the certified domination number increases on the removal of any edge/vertex as well as the class of stable graphs where the certified domination number remains unchanged on the removal of any edge/vertex. We point out that by Corollary 4.1, the class of critical (resp. stable) (with respect to the certified domination number) graphs with minimum degree is the same as the class of critical (resp. stable) graphs with respect to domination number, see for example [21–23]. Therefore, we are left with characterising critical (resp. stable) graphs with minimum degree
. This is an open problem.
The problem of constructive characterisations of trees with equal domination parameters has received attention in the literature, see for example [24,3,25,26], to mention but a few recent. Following this concept, we leave as an open problem to provide a constructive characterisation of -trees, that is, the class of trees with
.
Finally, let be a graph with no isolated vertex. Then no minimal dominating set of
has a shadowed vertex. Consequently, if
, then none of
-sets of
has a shadowed vertex. (In particular, it follows from Corollary 4.1 that if
has no weak support or
, then none of
-sets of
has a shadowed vertex.) A natural question then is whether the existence of a
-set with no shadowed vertex implies the equality of the numbers
and
. The answer to this question is not positive in general. For example, if
is a positive integer and
is the tree of order
obtained from the corona
by subdividing each of its edges exactly once, that is,
, then it is a routine exercise to check that
,
, and
has a
-set with no shadowed vertex, see for an illustration. Therefore, we conclude our paper with the problem of characterising all graphs having a minimum certified dominating set with no shadowed vertex.
Acknowledgement
We would like to thank the referee for the remarkable comments and suggestions that improved the presentation of our results. R. Ziemann was supported by the grant BW 538-5300-B865-15.
References
- HaynesT.W., HedetniemiS.T., SlaterP.J., Fundamentals of Domination in Graphs 1998Marcel Dekker New York
- HaynesT.W., HedetniemiS.T., SlaterP.J., Domination in Graphs: Advanced Topics 1998Marcel Dekker New York
- HenningM.A., RallD.F., On graphs with disjoint dominating and 2-dominating sets, Discuss. Math. Graph Theory, 33 2013 139–146
- DiestelR., Graph Theory 2012Springer Heidelberg
- KikunoT., YoshidaN., KakudaY., The NP-completeness of the dominating set problem in cubic planar graphs, IEICE Trans., E63 1980 443–444
- J. Suomela, Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete? (Posted by Florent Foucaud) Theoretical Computer Science Stack Exchange:http://cstheory.stackexchange.com/questions/2505 [2016-01-08].
- FinkJ.F., JacobsonM.S., KinchL.F., RobertsJ., On graphs having domination number half their order, Period. Math. Hungar., 16 1985 287–293
- ToppJ., VestergaardP.D., Well irredundant graphs, Discrete Appl. Math., 63 1995 267–276
- BalbuenaC., HansbergA., HaynesT.W., HenningM.A., Total domination edge critical graphs with total domination number three and many dominating pairs, Graphs Combin., 31 2015 1163–1176
- BurgerA.P., de VilliersA.P., van VuurenJ.H., Edge stability in secure graph domination, Discrete Math. Theor. Comput. Sci., 17 2015 103–122
- ChenX.-G., FujitaS., FuruyaM., SohnM.Y., Constructing connected bicritical graphs with edge-connectivity 2, Discrete Appl. Math., 160 2012 488–493
- EdwardsM., MacGillivrayG., The diameter of total domination and independent domination vertex-critical graphs, Australas. J. Combin., 52 2012 33–39
- NordhausE.A., GaddumJ., On complementary graphs, Amer. Math. Monthly, 63 1956 175–177
- AouchicheM., HansenP., A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math., 161 2013 466–546
- BorowieckiM., On the external stability number of a graph and its complement, Prace Nauk. Inst. Mat. Politech. Wrocaw., 12 1976 39–43
- CockayneE.J., HedetniemiS.T., Toward a theory of domination in graphs, Networks, 7 1977 247–261
- JaegarF., PayanC., Relations du type Nordhaus-Gaddum pour le nombre d’absorption d’un graphe simple, C. R. Acad. Sci. Paris A, 274 1972 728–730
- LaskarR., PetersK., Vertex and edge domination parameters in graphs, Congr. Numer., 48 1985 291–305
- DunbarJ.E., HaynesT.W., HedetniemiS.T., Nordhaus-Gaddum bounds for domination sums in graphs with specified minimum degree, Util. Math., 67 2005 97–105
- JosephJ.P., ArumugamS., Domination in graphs, Int. J. Manage. Syst., 11 1995 177–182
- BrighamR.C., ChinnP.Z., DuttonR.D., Vertex domination-critical graphs, Networks, 18 1988 173–179
- FulmanJ., HansonD., MacGillivrayG., Vertex domination-critical graphs, Networks, 25 1995 41–43
- ManimuthuY., KumarasamyK., Domination Stable Graphs 2012Lambert Academic Publishing Saarbrücken
- CymanJ., Total outer-connected domination in trees, Discuss. Math. Graph Theory, 30 2010 377–383
- HouX., A characterization of (2γ,γp)-trees, Discrete Math., 308 2008 3420–3426
- LuY., HouX., XuJ.-M., LiN., A characterization of (γt,γ2)-trees, Discuss. Math. Graph Theory, 30 2010 425–435