EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 16, No. 4, 2023, 2763-2774
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

Certified Perfect Domination in Graphs

Jamil J. Hamja
Office of the Vice Chancellor for Academic Affairs, MSU-Tawi-Tawi College of Technology
and Oceanography, 7500 Tawi-Tawi, Philippines

Abstract. Let G = (V,E) be a simple connected graph. A set S ⊆ V (G) is called a certified
perfect dominating set of G if every vertex v ∈ V (G) \ S is dominated by exactly one element
u ∈ S, such that u has either zero or at least two neighbors in V (G)\S. The minimum cardinality
of a certified perfect dominating set of G is called the certified perfect domination number of G
and denoted by γcerp(G). A certified perfect dominating set S of G with |S| = γcerp(G) is called
a γcerp-set. In this paper, the author focuses on several key aspects: a characterization of the
certified perfect dominating set, determining the exact values of the certified perfect domination
number for specific graphs, and investigating the certified perfect domination number of graphs
resulting from the join and corona of graphs. Furthermore, the relationship between the perfect
dominating set, and the certified perfect dominating set of a graph G are established.

2020 Mathematics Subject Classifications: 05C69,05C38,05C76

Key Words and Phrases: Certified domination, perfect domination, certified perfect domination

1. Introduction

In 1970, dominating sets were investigated in the context of social networks, where
vertices represented individuals and edges represented relationships between them. The
concept of dominating set helps to identify key individuals who could exert influence or
control over the entire network. However, the concept quickly found applications in various
other fields, including computer science, operations research, and biology.

In 2018, Dettlaff et. al, introduced the concept of certified dominating set in a graphs.
Therein, they presented the exact values of the certified domination number for some
classes of graphs as well as provided some upper bounds on this parameter for arbitrary
graphs. They then characterised a wide class of graphs with equal domination and certified
domination numbers and characterise graphs with large values of certified domination
numbers [4]. Moreover, several authors investigated further in this concept. They obtained
the certified domination number of Cartesian product, Corona product of some standard
graphs and special Subdivision graphs of certain families of graphs (see [9] [1], [8] and [10]).

DOI: https://doi.org/10.29020/nybg.ejpam.v16i4.4894

Email address: jamilhamja@msutawi-tawi.edu.ph (J. Hamja)

https://www.ejpam.com 2763 © 2023 EJPAM All rights reserved.



J. Hamja / Eur. J. Pure Appl. Math, 16 (4) (2023), 2763-2774 2764

In 1990, Livingston M. et.al, investigated the concept of perfect dominating set of a
graph. They studied the existence and construction of perfect dominating sets in families
of a graphs arising from the interconnection networks of parallel computers. These include
trees, dags, series-parallel graphs, meshes, tori, hypercubes, cube-connected cycles, cube-
connected paths, and de Bruijn graphs [7]. In 2014, Kwon Y.S. et. al., got some results
related to perfect domination sets of Cayley graphs. They showed that if a Cayley graph
C(A, X) has a perfect dominating set S which is a normal subgroup of A and whose
induced subgraph is F , then there exists an F -bundle projection p : C(A, X) → Km for
some positive integer m [6]. Moreover, numerous classes of graphs have been investigated
to explore variations and parameters of the perfect dominating set (see [3], [11] and [2]).

Now, let us consider a scenario, denoted as G, where we are given a set of officials,
denoted as S ⊆ V (G), and a set of civilians, denoted as H = V (G) \ S. For each civilian,
represented by x ∈ H, it is necessary to have precisely one official, denoted as u ∈ S, who
can serve that civilian. Furthermore, whenever such an official u serves a civilian x, there
must exist another civilian, denoted as y ∈ H, who only observes the service provided by
the official u to civilian x. In other words, y acts as a witness, ensuring that there is no
abuse or misconduct from official u.

The question arises: What is the minimum number of officials required to guarantee
such a service, considering a given social network? This problem leads us to introduce the
concept of a certified perfect dominating set of a graph G.

2. Terminology and Notation

This section comprises essential definitions required for the study.

Let G = (V,E), where V represents the vertex set of G and E represents the edge set
of G. The elements of V (G) are called vertices and the cardinality |V (G)| of V is the
order of G. The elements of E(G) are called edges and the cardinality |E(G)| of E is
the size of G. The degree of a vertex v, denoted as deg(v), refers to the number of edges
incident with v. The maximum degree among all vertices in G is denoted as ∆(G). The
open neighborhood of a vertex u in G is the set of its neighboring vertices and is denoted as
NG(u) = {v ∈ V (G) : uv ∈ E(G)}. The closed neighborhood of u in G is the open neigh-
borhood of u along with the vertex u itself, expressed as NG[u] = NG(u) ∪ {u}. Similarly,
the closed neighborhood of a subset S of V (G), denoted as NG[S] = ∪v∈SNG[v], represents
the set of vertices in G that are either in S or are adjacent to a vertex in S.

The join of two graphs G and H, denoted by G + H, is the graph with
V (G+H) = V (G) ∪ V (H) and E(G+H) = E(G) ∪E(H) ∪ {uv : u ∈ V (G), v ∈ V (H)}.
The corona of graphs G and H, G ◦H, is the graph obtained by taking one copy of G and
|V (G)| copies of H, and then joining the ith vertex of G to every vertex of the ith copy
of H. For every v ∈ V (G), denote by Hv the copy of H whose vertices are attached one
by one to the vertex v. Subsequently, denote by v+Hv the subgraph of the corona G ◦H



J. Hamja / Eur. J. Pure Appl. Math, 16 (4) (2023), 2763-2774 2765

corresponding to the join ⟨{v}⟩+Hv, v ∈ V (G) [5].

A set S ⊆ V (G) is called dominating set if NG[S] = V (G). A dominating set S is
a minimal dominating set if no proper subset S′ ⊂ S is a dominating set. A minimum
cardinality of a dominating set of G is called domination number of G, and is denoted by
γ(G). A dominating set S with |S| = γ(G) is called a γ-set.

A dominating set S ⊆ V (G) is called certified dominating set of G if every vertex v ∈ S
has either zero or at least two neighbors in V (G) \S. A minimum cardinality of a certified
dominating set of G is called certified domination number of G and denoted by γcer(G). A
certified dominating set of S with |S| = γcer(G) is called a γcer-set [4].

A set S ⊆ V (G) is called perfect dominating set if every vertex v ∈ V (G) \ S is
dominated by exactly one element in S. The minimum cardinality of a perfect dominating
set of G is called perfect domination number, and is denoted by γp(G). A perfect dominating
set S with |S| = γp(G) is said to be a γp-set [7].

A perfect dominating set S ⊆ V (G) is called certified perfect dominating set of G if
every u ∈ S has either zero or at least two neighbors in V (G) \ S. A minimum cardinality
of a certified perfect dominating set of G is called certified perfect domination number of
G and denoted by γcerp(G). A certified perfect dominating set S of G with |S| = γcerp(G)
is called a γcerp-set.

Example 1. Consider the three subsets S1, S2, and S3 of the graph G shown in Figure
1. First, let S1 = {a, e, g, j, n, r} ⊆ V (G) be a first dominating set of G. Observe that all
vertices a, e, g, j, n, r ∈ S1 have at least two neighbors in V (G) \ S1. Thus, S1 is a certified
dominating set of G, and γcer(G) = |S1| = 6. However, S1 is not a perfect dominating
set since there exist vertices b, c, d ∈ V (G) \ S1 dominated by two vertices a, e ∈ S, and
vertex f ∈ V (G) \ S1 is dominated by e, f ∈ S1. Therefore, S1 is not a certified perfect
dominating set of G.

Second, let S2 = {a, b, g, j, n, r} ⊆ V (G) be a second dominanting set of G. Observe
that all vertices in V (G) \ S2 are dominated by exactly one vertex in S2. Thus, S2 is a
perfect dominating set of G, and γp(G) = |S2| = 6. However, S2 is not a certified domi-
nating set of G since there exists vertex b ∈ S2 that has only one neighbor in V (G) \ S2.
Therefore, S2 is not a perfect certified dominating set of G.

Lastly, let S3 = {a, b, c, d, e, f, g, j, n, r} ⊆ V (G) be a third dominating set of G. Observe
that all vertices in V (G) \ S3 are dominated by exactly one vertex in S3, and all vertices
in S3 have either zero or at least two neighbors in V (G) \ S3. Therefore, S3 is a certified
perfect dominating set of G, and γcerp(G) = |S3| = 10.



J. Hamja / Eur. J. Pure Appl. Math, 16 (4) (2023), 2763-2774 2766

a

b

rc

e

i jh

m

s

l n

qp

f

G :

k

od g

Figure 1: Graph G with γcerp(G) = 10

3. Main Results

Proposition 1. Let G be a connected graph of order n. Then every support vertex of G
belongs to every certified perfect dominating set of G.

Proof. Assume that S is a certified perfect dominating set of G. Let u be a support
vertex of G, and v be a leaf adjacent to u. If u /∈ S, then v ∈ S. However, since v would
have only one neighbor in V (G) \ S, S is not a certified dominating set of G. Therefore,
we can conclude that S cannot be a certified perfect dominating set. This contradicts the
initial assumption that S is a certified perfect dominating set.

Theorem 1. For any graph G of order n, γp(G) ≤ γcp(G) ≤ n.

Proof. Let G be a graph of order n. Let us first show its upper bounds. Let S1 be
a perfect dominasting set, and S2 be a certified perfect dominating set of G. Since every
certified perfect dominating set S1 ⊆ S2, γp(G) ≤ γcerp(G). So, we are left to show its
lower bounds. Since every certified dominating set S2 ⊆ V (G), γcerp(G) ≤ |V (G)| = n.
Therefore, the assertion holds.

Theorem 2. Let a and b positive integers with 1 ≤ a ≤ b. Then there exists a connected
graph G such that γp(G) = a and γcerp(G) = b.

Proof. Consider the following cases:
Case 1: a = b
Let G1 be the graph shown in Figure 2. Let S = {x1, x2, . . . , xc−1, xc, } ⊆ V (G1). Then S
is both γp-set and γcerp-set of G. Therefore, a = γp(G3) = γcerp(G3) = b.

Case 2: a < b.
Let G2 be the graph shown in Figure 3 and Figure 4 for γp(G2) and γcerp(G2), respectively.
Let n = b−a and a = c+n with c ≥ 2 and n ≥ 2. Let S = {x1, x2, . . . , xc−1, xc, y1, y2, . . . , yn}
and S∗ = S ∪ {z1, z2, . . . , zn}. Hence, γp(G2) = |S| = c + n = a and γcerp(G2) = |S∗| =
c+ n+ n = a+ n = b.



J. Hamja / Eur. J. Pure Appl. Math, 16 (4) (2023), 2763-2774 2767

...x1

x2

x3

xc−1

xc
G1:

Figure 2: Graph G1 with γp(G1) = γcerp(G1)

...x1

x2

x3

xc−1

xc
G2 :

...

y1

y2

yn

...

z1

z2

zn

Figure 3: Graph G2 with γp(G2) = a

...x1

x2

x3

xc−1

xc
G2 :

...

y1

y2

yn

...

z1

z2

zn

Figure 4: Graph G2 with γcerp(G2) = b

Consequently, The statement is substantiated by this evidence. Therefore, this com-
pletes the proof.



J. Hamja / Eur. J. Pure Appl. Math, 16 (4) (2023), 2763-2774 2768

Theorem 3. Let G be a graph with components G1, G2, . . . , Gk, where k ≥ 2. Then

γcp(G) =
k∑

i=1

γcp(Gi).

Proof. Let Si be a γcerp-set of Gi for each i ∈ {1, 2, . . . , k}. Then S =
⋃k

i=1 Si forms a
γcerp-set of G. Therefore, we have

γcerp(G) ≤ |S| =
k∑

i=1

|Si| =
k∑

i=1

γcerp(Gi).

Conversely, suppose S∗ is a γcerp-set of G. For each i ∈ {1, 2, . . . , k}, let S∗
i = S∗ ∩

V (Gi). Since S∗ is a γcerp-set of G, S∗
i is a γcerp-set of Gi for each i ∈ {1, 2, . . . , k}. This

implies that

γcerp(G) = |S∗| =
k∑

i=1

|S∗
i | ≥

k∑
i=1

γcerp(Gi).

Therefore, γcerp(G) =
∑k

i=1 γcerp(Gi).

Theorem 4. For a path Pn of order n ≥ 1,

γcerp(Pn) =

{
n
3 if n ≡ 0 (mod 3);

n otherwise.

Proof. Suppose that V (Pn) = {v1, v2, . . . , vn−1, vn} such that deg(v1) = deg(vn) = 1
and deg(vi) = 2 for each i ∈ {2, 3, . . . , n− 1}. Consider the following cases:

Case 1. Suppose that n ≡ 0 (mod 3). Suppose that n = 3. Then γcerp(P3) = 1 = 3
3 .

Suppose that n > 3. Let q = n
3 and r ∈ {1, 2, . . . , q − 1, q}. Then let us denote a group of

vertices of Pn into q disjoint subsets Gr, these are,

G1 = {v1, v2, v3}
G2 = {v4, v5, v6}

...
Gq = {vn−2, vn−1, vn}

Clearly, the set S = {v2, v5, . . . , vn−4, vn−1} ⊆ V (Pn) is a γcerp-set of Pn

since NG[S] = V (Pn) and every vertex vj ∈ V (Pn), j ∈ {2, 5, . . . , n − 4, n − 1}
has two neighbors in V (Pn) \ S. It follows that all other vertices vi ∈ V (Pn) \ S,
i ∈ {1, 3, 4, . . . , n − 3, n − 2, n} are dominated by exactly one vertex in S. Therefore,
γcerp(Pn) = |S| = n

3 .



J. Hamja / Eur. J. Pure Appl. Math, 16 (4) (2023), 2763-2774 2769

Case 2. Suppose that n ≡ 1(mod3). Clearly if n = 1, γcerp(P1) = 1. Suppose that
n = 4. Let S1 = {v1, v2, v3, v4}. Observe that every vertex in S1 has zero neighbor in
V (P4) \ S1, this means that γcerp(S1) = |S1| = 4. Suppose that n ≥ 4. Let q = n

4 and
r ∈ {1, 2, . . . , q− 1, q}. Then let us denote a group of vertices of Pn into q disjoint subsets
as Gr, these are,

G1 = {v1, v2, v3, v4}
G2 = {v5, v6, v7, v8}

...
Gq = {vn−3, vn−2, vn−1, vn}.

Clearly, the set S
′
=

⋃n
r=1 Sr is a γcerp-set of Pn since NG[S

′
] = V (Pn) and every vertex

vj ∈ V (Pn), j ∈ {1, 2, . . . , n−1, n} has zero neighbor in V (Pn)\S
′ . Consequently,γcerp(Pn) =

|S′ |= |V (Pn)|= n.

Case 3. Suppose that n ≡ 2 (mod 3). Clearly, if n = 2, then γcerp(P2) = 2. Suppose
that n = 5. Let S1 = {v1, v2, v3, v4, v5}. Observe that every vertex in S1 has zero neighbor
in V (P5) \ S1. Thus, γcerp(S1) = |S1| = 5. Let q = n

5 and r ∈ {1, 2, . . . , q − 1, q}. Then let
us denote a group of vertices of Pn into q disjoint subsets as Gr, these are,

G1 = {v1, v2, v3, v4, v5}
G2 = {v6, v7, v8, v9, v10}

...
Gq = {vn−5, vn−4, vn−3, vn−2, vn−1, vn}.

Clearly, the set S
′′
=

⋃n
r=1 Sr, r ∈ {1, 2, . . . , q − 1, q} is a γcerp-set of Pn since NG[S

′′
] =

V (Pn) and every vertex vj ∈ V (Pn), j ∈ {1, 2, . . . , n−1, n} has zero neighbor in V (Pn)\S
′′ .

Consequently, γcerp(Pn) = |S′′ |= |V (Pn)|= n.

Theorem 5. For a cycle Cn of order n ≥ 3,

γcerp(Cn) =

{
n
3 if n ≡ 0 (mod 3);

n otherwise.

Proof. Suppose that V (Cn) = {v1, v2, . . . , vn−1, vn} such that deg(vi) = 2,
i ∈ {1, 2, . . . , n− 1, n}. Consider the following cases:

Case 1: Suppose that n ≡ 0 (mod 3). If n = 3. then γcerp(C3) = 1 = 3
3 . Suppose that

n > 3. Let q = n
3 and r ∈ {1, 2, . . . , q − 1, q}. Then let us denote a group of vertices of Cn

into q disjoint subsets Hr, these are,

H1 = {v1, v2, v3}



J. Hamja / Eur. J. Pure Appl. Math, 16 (4) (2023), 2763-2774 2770

H2 = {v4, v5, v6}
...

Hq = {vn−2, vn−1, vn}

Clearly, the set S = {v2, v5, . . . , vn−4, vn−1} ⊆ V (Cn) is a γcerp-set of Cn since NG[S] =
V (Cn) and every vertex vj ∈ V (Cn), j ∈ {2, 5, . . . , n − 4, n − 1} has two neighbors in
V (Cn)\S. Furthermore, every vertex vi ∈ V (Cn)\S, i ∈ {1, 3, 4, 6, . . . , n−5, n−3, n−2, n}
is dominated by exactly one vertex in S. Therefore, γcerp(Cn) = |S| = n

3 .

Case 2. Suppose that n ≡ 1(mod3). Suppose that n = 4. Let S1 = {v1, v2, v3, v4}.
Observe that every vertex in ∈ S1 has zero neighbor in V (C4) \ S1. This means that
γcerp(S1) = |S1| = 4. Suppose that n > 4. Let q = n

4 and r ∈ {1, 2, . . . , q − 1, q}. Then let
us denote a group of vertices of Cn into q disjoint subsets as Hr, these are,

H1 = {v1, v2, v3, v4}
H2 = {v5, v6, v7, v8}

...
Hq = {vn−3, vn−2, vn−1, vn}.

Clearly, the set S∗ =
⋃n

r=1 Sr is a γcerp-set of Cn since NG[S
∗] = V (Cn) and every ver-

tex vj ∈ V (Cn), j ∈ {1, 2, . . . , n − 1, n} has zero neighbor in V (Cn) \ S∗. Consequently,
γcerp(Cn) = |S∗| = |V (Cn)| = n.

Case 3. Suppose that n ≡ 2(mod3). Suppose that n = 5. Let S1 = {v1, v2, v3, v4, v5}.
Observe that every vertex in ∈ S1 has zero neighbor in V (C5) \ S1. Thus, γcerp(S1) =
|S1| = 5. Suppose that n > 5. Let q = n

5 and r ∈ {1, 2, . . . , q−1, q}. Further, let us denote
a group of vertices of Cn into q disjoint subsets as Hr, these are,

H1 = {v1, v2, v3, v4, v5}
H2 = {v6, v7, v8, v9, v10}

...
Hq = {vn−5, vn−4, vn−3, vn−2, vn−1, vn}.

Clearly, the set S∗∗ =
⋃n

r=1 Sr is a γcerp-set of Cn since NG[S
∗∗] = V (Cn) and every vertex

vj ∈ V (Cn), j ∈ {1, 2, . . . , n − 1, n} has zero neighbor in V (Cn) \ S∗∗. Consequently,
γcerp(Cn) = |S∗∗| = |V (Cn)| = n.

Theorem 6. For a complete Kn of order n,

γcerp(Kn) =

{
1 if n = 1or n ≥ 3;

2 if n = 2.



J. Hamja / Eur. J. Pure Appl. Math, 16 (4) (2023), 2763-2774 2771

Proof. Suppose that Kn be a complete graph of order n ≥ 1 such that every pair of
distinct vertices are adjacent. Consider the following cases:

Case 1. Suppose that n = 1 or n ≥ 3. If n = 1, then γcerp(K1) = 1. Suppose that
n ≥ 3. Let S = {v1} ⊆ V (Kn). Since NKn [S] = V (Kn), all vertices in V (Kn) \ S are
dominated by exactly one vertex v ∈ S and vertex v ∈ S has at least two neighbors in
V (Kn) \ S. Therefore, γcerp(Kn) = |S|= 1.

Case 2. Suppose that n = 2. Then γcerp(K2) = 2.

Theorem 7. For a complete bipartite Km,n with m,n vertices,

γcerp(Km,n) =


1, if m = 1or n = 1;

4, if m = n = 2.

2, otherwise.

Proof. Let m and n be a positive integers. Suppose that Km,n be a complete bipartite
graph whose vertices can be partitioned into two disjoint sets such that every vertex in one
set U of order m is connected to every vertex in the other set V of order n. Consider the
following cases:

Case 1. Suppose that m = 1 or n = 1. Clearly, If m = 1, then γcerp(K1,m) = 1.
Similarly, if n = 1, then γcerp(Km,1) = 1.

Case 2. Suppose that m = n = 2. Then Km,n = K2,2. Then K2,2
∼= C4. Therefore, by

Theorem 5, γcerp(K2,2) = 4.

Case 3. Suppose that m,n ≥ 3. Write Km,n = Km + Kn = U + V . Let S =
{u1, v1} ⊆ V (Km,n), where u1 ∈ U and v1 ∈ V . Observe that for every vertex ui ∈ U \ S,
i ∈ {1, 2, . . . ,m − 1,m} is dominated by exactly one vertex v1 ∈ S and v1 has at least
two neighbors in V (Km,n) \ S since m ≥ 3. Similarly, for every vertex vj ∈ V \ S,
j ∈ {1, 2, . . . , n−1, n}is dominated by exactly one u1 ∈ S and u1 has at least two neighbors
in V (Km,n) \ S since n ≥ 3. Furthermore, NG[S] = V (Km,n). Therefore, γcerp(Km,n) =
|S| = 2.

4. Certified Perfect Domination Number in the Join of two Graphs

This section presents the outcomes obtained when the graph G+H possesses a γcerp-set
along with its certified perfect domination number.

Theorem 8. Let G be a graph of order n ≥ 3. Then γcerp(G) = 1 if and only if
G = K1 +H for some graph H of order n ≥ 2.



J. Hamja / Eur. J. Pure Appl. Math, 16 (4) (2023), 2763-2774 2772

Proof. Suppose γcerp(G) = 1. Then there exists a dominating set S ⊆ V (G) consisting
of a single vertex, that is, S = {v}. Consequently, every vertex in V (G) \ S is dominated
by v ∈ S. Therefore, S is a perfect dominating set of G. This means that NG(v) = |V (H)|
for some graph H of order n ≥ 2. Thus, S is a certified dominating set of G. From these
observations, we conclude that S is a certified perfect dominating set of G = K1 +H.

Conversely, suppose that G = K1 + H for some H is a graph of order n ≥ 2. Let
S = V (K1). Then S = {v}. Since every vertex in V (H) is dominated by exactly one
vertex v ∈ S and vertex v ∈ S has at least two neighbors. Therefore, γcerp(G) = |S| = 1.

Proposition 2. If S is a dominating set or a perfect dominating set of G with |S| = 1,
then S is a certified perfect dominating set of G. In particular, γ(G) = γp(G) if and only
if γcerp(G) = 1.

The next result follows from Theorem 8 and Proposition 2

Corollary 1. The following are graphs having γcerp(G) = 1:

i. star graph Sn = K1 +Kn, n ≥ 2.

ii. fan graph Fn = K1 + Pn, n ≥ 2.

iii. wheel Wn = K1 + Cn, n ≥ 3.

iv. friendship graph Frn = K1 + nP1, n ≥ 2.

v. windmill graph Wm
n = K1 +mKn−1, m ≥ 2 and n ≥ 3.

vi. complete bipartite graph Km,n = Km +Kn, m = 1 or n = 1.

Corollary 2. Let G and H be any graph of order m and n, respectively with γ(G) = 1 or
γ(H) = 1. Then γcerp(G+H) = 1.

Proposition 3. Let G and H be a trivial graphs. Then γcerp(G+H) = 2.

Proof. Clearly, If G and H are graphs of order m = 1 and n = 1, respectively. Then
γcerp(G+H) = 2.

Proposition 4. Let G and H be any connected non-trivial graph of order m and n, re-
spectively with γ(G) ̸= 1 or γ(H) ̸= 1. Then γcerp(G+H) = |V (G+H)|.

5. The Certified Perfect Domination in the Corona of Graphs

In this section presents the γcerp-set of G ◦ H and its certified perfect domination
number.



J. Hamja / Eur. J. Pure Appl. Math, 16 (4) (2023), 2763-2774 2773

Theorem 9. Let G be a connected graph of order m and H be any graph of order n ≥ 2.
Then a subset S of V (G ◦H) is a certified perfect dominating set of G ◦H if and only if
S ∩ V (v +Hv) is a certified perfect dominating set of v +Hv for every v ∈ V (G).

Proof. Let S ⊆ G ◦H be a certified perfect dominating set of G ◦H and let v ∈ V (G).
If v ∈ S, then v is a certified perfect dominating set of v +Hv since H is any graph with
vertices n ≥ 2. Suppose that v /∈ S. Let a ∈ V (v + Hv) \ S, where a ̸= v. Since S is a
certified perfect dominating set of G ◦H, there exist b ∈ S such that ab ∈ E(G ◦H). This
means that b ∈ V (v +Hv) ∩ S and ab ∈ E(v +Hv). This proves that S ∩ V (v +Hv) is a
certified perfect dominating set of v +Hv.

Conversely, suppose that S ∩ V (v+Hv) is a certified perfect dominating set of v+Hv

for every v ∈ V (G). Indeed, S is a certified perfect dominating set of G ◦H.

Corollary 3. If G is a connected graph of order m and H be any graph of order n ≥ 2.
Then γcerp(G ◦H) = m.

Proof. Let S ⊆ V (G ◦ H). Suppose that S = V (G). Then S ∩ V (v + Hv) = v is
a certified perfect dominating set of v + Hv for every v ∈ V (G) since H is any graph
with vertices n ≥ 2. This implies that S is a certified perfect dominating set of G ◦H by
Theorem 9. Consequently, γcerp(G◦H) ≤ |S| = m. Moreover, if S∗ is a minimum certified
perfect dominating set of G ◦H, then V (S∗ ∩ v+Hv) is a certified perfect dominating set
of v + Hv for every v ∈ V (G) since H is any graph with vertices n ≥ 2 by Theorem 9.
This means that γcerp(G ◦H) = |S∗| ≥ m. Consequently, γcerp(G ◦H) = m.

Theorem 10. Let G be a connected graph of order m and H be a trivial graph. Then
γcerp(G ◦H) = 2m.

Proof. Let S1 be a vertex set of a connected graph G of order m and S2 be a vertex
set of a trivial graph H. Since H ∼= K1, V (H) are pendant vertices of G ◦H. This means
that |S2| = |S1| = m. Furthermore, every vertex in v ∈ V (v +Hv) has only one neighbor
in V (v +Hv) \ v for every v ∈ S1. Hence, S1 ∪ S2 is a certified perfect dominating set of
G ◦H. Therefore γcerp(G ◦H) = |V (G ◦H)| = |S1|+ |S2| = m+m = 2m

6. Conclusion and Recommendation

The study has introduced and examined the concept of a certified perfect dominating
set, denoted as S, within the context of graph G. The author’s primary focus has been on
several critical areas: characterizing the certified perfect dominating set, determining pre-
cise values for the certified perfect domination number in specific graphs, and exploring the
certified perfect domination number in graphs resulting from join and corona operations.
Furthermore, the study has established relationships between the perfect dominating set
and the certified perfect dominating set of graph G.



REFERENCES 2774

Researchers interested in this concept can further investigate it in various graph prod-
ucts that were not addressed in this paper. Additionally, they may explore and analyze its
bounds in relation to other well-established parameters in graph theory.

Acknowledgements

The author would like to thank the anonymous referees for their comments and sug-
gestions which led to the betterment of the paper. This study has been supported by
Mindanao State University - Tawi-Tawi College of Technology and Oceanography.

References

[1] V. G. Bhagavathi Ammal and R. Louisa Dickfania. Accurate Certified Domination
Number of Graphs. International Journal of Mathematics Trends and Technology,
66(05):90–98, 2020.

[2] C. L. Armada and J. J. Hamja. Perfect Isolate Domination in Graphs. Europian
Journal of Pure and Applied Mathematics., 16:1326–1341, 2023.

[3] B. Chaluvaraju, M. Chellali, and K. A. Vidya. Perfect k-domination in Graphs.
Autraliasian Journal of Combinatorics, 48:175–184, 2010.

[4] M. Dettlaff, M. Lemanska, R. Ziemann J. Topp, and P. Zylinski. Certified Domination.
AKCE International Journal of Graphs and Combinatirics, 09(004):1–12, 2018.

[5] F. Harary. Graph Theory. Addison-Wesley Publishing Company, Inc., USA, 1969.

[6] Y. S. Kwon and J. Lee. Perfect Domination Sets in Cayley Graphs. Discrete Applied
Mathematics, 162:259–263., 2014.

[7] M. Livingston and Q. F. Stout. Perfect Dominating Sets. Congressus Numerantium.,
79:187–203., 1990.

[8] S. Durai Raj, S. G. Shiji Kumari, and A. M. Anto. Certified Domination Number in
Corona Product of Graphs. Malaya Journal of Matematik, 9(1):1080–1082, 2021.

[9] S. Durai Raj and S.G. Shiji Kumari. Certified Domination Number in Product of
Graphs. Turkish Journal of Computer and Mathematics Education, 11(03):1166–1170,
2020.

[10] S. Durai Raj, S.G. Shiji Kumari, and A.M. Anto. Certified Domination Num-
ber in Subdivision of Graphs. International Journal of Mechanical Engineering.,
06(03):4324–4327., 2021.

[11] R. C. Rakim, CJ C. Saromines, and H. M. Rara. Perfect Hop Domination in Graphs.
Applied Mathematical Sciences, 12(13):635–649., 2018.