EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 17, No. 3, 2024, 2196-2209
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

Restrained Global Defensive Alliances in Graphs

Leocint F. Consistente1,∗, Isagani S. Cabahug, Jr.1

1 Department of Mathematics, College of Arts and Sciences, Central Mindanao University,
Musuan, 8710 Maramag, Bukidnon, Philippines

Abstract. A defensive alliance in a graph G is a nonempty set of vertices S ⊆ V (G) such that
for every vertex v ∈ S, |N [v] ∩ S| ≥ |N(v) ∩ (V (G)∖ S)|. A defensive alliance S is called global if
every vertex in V (G)∖ S is adjacent to at least one member of the alliance S. In this paper, the
concept of restrained global defensive alliance in graphs was introduced. In particular, a global
defensive alliance S is a restrained global defensive alliance if the induced subgraph of V ∖ S has
no isolated vertex. Here, some properties of this alliance were identified, and its bounds were also
determined. In addition, the restrained global defensive alliance number was also formulated, along
with characterizations of some special classes of graphs, specifically complete, complete bipartite,
and path graphs.

2020 Mathematics Subject Classifications: 05C69

Key Words and Phrases: Restrained domination, defensive alliance, global defensive alliance,
restrained global defensive alliance

1. Introduction

An alliance refers to a gathering of individuals, organizations, or states aimed at achiev-
ing a common goal, mutual protection, or asserting dominance over those outside the al-
liance. For this reason, Kristiansen and colleagues explored and developed defensive and
offensive alliances in the graphs [12].

In defensive alliances, the collaboration of nodes or entities achieved mutual security
and protection. They established resilient networks capable of withstanding external in-
fluences and pressure. If these alliances were also dominating, then they are called global
defensive alliances [11].

Global offensive alliances and global defensive alliances have been a focus of study
among mathematics enthusiasts. Some of these studies include global offensive alliances
in some special classes of graphs in 2011 by Cabahug and Isla [3], global defensive alliances
in the lexicographic product of paths and cycles in 2020 by Barbosa, Dourado, and Da

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v17i3.5156

Email addresses: coleocint@gmail.com (L. Consistente),
isaganicabahugjr@cmu.edu.ph (I. Cabahug, Jr.)

https://www.ejpam.com 2196 © 2024 EJPAM All rights reserved.



L. Consistente, I. Cabahug, Jr. / Eur. J. Pure Appl. Math, 17 (3) (2024), 2196-2209 2197

Silva [1], and global defensive k-alliances in directed graphs focusing on combinatorial and
computational issues in 2020 by Mojdeh, Samadi, and Yero. Moreover, in 2022, Gaikwad
and Maity studied globally minimal defensive alliances [9].

Domination in graphs is a growing area of research. Some recent studies on domination
can be found in [4], [6], and [14]. On the other hand, in 1999, Hedetniemi and colleagues
introduced the notion of a restrained dominating set wherein the subgraph induced by its
complement has no isolated vertices [7]. Some studies related to restrained domination
include fair restrained domination in graphs in 2020 by Enriquez [8] and restrained double
Roman domination of a graph in 2022 by Mojdeh, Masoumi, and Volkmann [13].

Although global defensive alliance forms a defensive alliance that is also a dominating
set, it could not guarantee an alliance where non-members were also adjacent to at least
one non-member. To address this, a new type of alliance had to be formed. With this
in mind, the authors decided to introduce restrained global defensive alliances in graphs.
Using this alliance as a basis, the authors aim to contribute new insights to applications re-
lated to strategic interactions and mutual support within networks by establishing certain
characterizations, developing formulas for the restrained global defensive alliance number,
and determining some of its inherent properties on complete, complete bipartite, and path
graphs.

2. Terminology and Notation

A graph G is a finite nonempty set V (G) of objects called vertices (the singular is
vertex) together with a possibly empty set E(G) of 2-element subsets of V (G) called
edges. Here, V (G) is the vertex set of a graph G while E(G) is the edge set of graph G
[5]. An edge joining a vertex to itself is called a loop. Two or more edges that join the
same pair of distinct vertices are called parallel edges. If a graph has no loops and parallel
edges then it is a simple graph. The order of a graph G refers to the number of vertices
in G while the size of a graph G refers to the number of edges in G [5]. If uv is an edge
of a graph G, then u and v are adjacent vertices. Two adjacent vertices are referred to as
neighbors of each other. The set of neighbors of a vertex v is called the open neighborhood
of v(or simply the neighborhood of v) and is denoted by NG(v), or N(v) if the graph G is
understood. The set N [v] = N(υ)

⋃
{υ} is called the closed neighborhood of v [5].

The degree of a vertex v in a graph G, denoted by deg v, is the number of vertices in G
that are adjacent to v. The largest degree among the vertices of G is called the maximum
degree of G, denoted by △(G), while the smallest degree among the vertices of G is called
the minimum degree of G, denoted by δ(G) [5]. A vertex of degree 0 is referred to as an
isolated vertex and a vertex of degree 1 is an end-vertex or a leaf [5].

For an integer n ≥ 1, the path Pn is a graph of order n and size n− 1 whose vertices
can be labeled by v0, v1, ..., vn−1 and whose edges are vivi+1 for i = 0, 1, 2, ..., n− 2 [5]. A
complete graph of order n, denoted by Kn, is graph with n vertices where in every pair
of distinct vertices are adjacent [10]. An empty graph of order n is graph with n vertices
where in every pair of distinct vertices are not adjacent [5]. A graph G is a complete
bipartite graph if V (G) can be partitioned into two sets A1 and A2 (called partite sets) so



L. Consistente, I. Cabahug, Jr. / Eur. J. Pure Appl. Math, 17 (3) (2024), 2196-2209 2198

that uv is an edge of G if and only if u ∈ A1 and v ∈ A2 . If |A1| = m and |A2| = n, then
this complete bipartite graph, denoted by Km,n (or Kn,m), has order m+ n and size mn.
The complete bipartite graph K1,n is called a star [5].

A graph H is a subgraph of a graph G if the vertex set V (H) of H is contained in
the vertex set V (G) of G and all edges of H are edges in G, i.e, V (H) ⊆ V (G) and
E(H) ⊆ E(G). For any vertex subset S ⊆ V (G), the induced subgraph by S denoted by
⟨S⟩G contains all the edges of E(G) whose extremities belong to S [2].

A set S of vertices of G is a dominating set if every vertex in V (G)∖S is adjacent to at
least one vertex in S. The minimum cardinality among the dominating sets of G is called
the domination number of G and is denoted by γ(G) . A dominating set of cardinality
γ(G) is then referred to as a minimum dominating set [5].

A restrained dominating set in a graph G is a set S ⊆ V (G) where every vertex in
V (G)∖S is adjacent to a vertex in S as well as another vertex in V (G)∖S. In this case,
the induced subgraph ⟨V (G) ∖ S⟩ has no isolated vertices. The restrained domination
number of G, denoted by γr(G), is the smallest cardinality of a restrained dominating set
of G [7].

A defensive alliance in a graph G is a nonempty set of vertices S ⊆ V (G) if for every
vertex v ∈ S, |N [v]∩S| ≥ |N(v)∩ (V (G)∖S)|. A defensive alliance S is called global if it
effects every vertex in V (G)∖ S, that is, every vertex in V (G)∖ S is adjacent to at least
one member of the alliance S. In this case, S is a dominating set. The global defensive
alliance number of G, denoted γa(G), is the minimum size around all the global defensive
alliances of G [11].

3. Results

This paper utilized the following terms to denote specific concepts: ds signified dom-
inating set, da represented defensive alliance, rds stood for restrained dominating set,
gda indicated global defensive alliance, and rgda denoted restrained global defensive al-
liance. Moreover, if G is a graph, its vertex set V (G) and edge set E(G) are denoted as V
and E, respectively. Additionally, graphs considered is this paper are simple, finite, and
undirected graphs.

Definition 1. A restrained global defensive alliance of a graph G = (V,E) is a set S of
vertices of G that is a restrained dominating set and global defensive alliance. A set S
with the least number of vertices is called a minimum restrained global defensive alliance.
The cardinality of a minimum restrained global defensive alliance is called the restrained
global defensive alliance number denoted by γra(G).

Example 1. In Figure 1, consider a set S = {v0, v1} in K4 = (V,E). Notice that
V ∖ S = {v2, v3}, and both v2 and v3 are adjacent to v0. This means that S is a ds.
Moreover, ⟨V ∖ S⟩ has no isolated vertices since v2 is adjacent to v3. This means that S
is an rds. Now, it remains to show that S is a da. Observe that

|N [v0] ∩ S| = |{v0, v1}| = 2 ≥ 2 = |{v2, v3}| = |N(v0) ∩ (V ∖ S)|



L. Consistente, I. Cabahug, Jr. / Eur. J. Pure Appl. Math, 17 (3) (2024), 2196-2209 2199

and
|N [v1] ∩ S| = |{v0, v1}| = 2 ≥ 2 = |{v2, v3}| = |N(v1) ∩ (V ∖ S)|.

Hence, S is a da. This implies that S is also a gda. Therefore, by Definition 1, S is an
rgda.

Figure 1: A Complete graph K4.

Theorem 1. Let G = (V,E) be any graph of order n ≥ 1. Then the set V is a restrained
global defensive alliance in G. As consequence, γra(G) ≤ n.

Proof. Let G = (V,E) be any graph of order n ≥ 1. Since V dominates itself and
V ∖ V is empty, it vacuously implies that V is an rds. For the same reason, notice that
for every v ∈ V , |N [v] ∩ V | = |N [v]| ≥ 0 = |∅| = |N(v) ∩ (V ∖ V )|. Hence, V is a da in
G. So, V is an rgda in G.

Now, if no set W ⊂ V is an rgda in G, then γra(G) = |V | = n. On the other
hand, if there exist a set W ⊂ V that is also an rgda in G, then γra(G) < n. Hence,
γra(G) ≤ n.

Theorem 2. Let G = (V,E) be a graph with leaf vertices. If S ⊆ V is a restrained global
defensive alliance in G, then S contains the leaf vertices of G.

Proof. Let S be an rgda in G = (V,E). Assume that S does not contain all the leaf
vertices of G. Then there must exist a leaf vertex v ∈ V such that v /∈ S. Suppose that v
is adjacent to a vertex a ∈ V . This leads to the following cases:

Case 1: a /∈ S.
Then no vertices in S can dominate v. This means that S is not a ds, a contra-
diction.

Case 2: a ∈ S.
Then ⟨V ∖ S⟩ contains an isolated vertex v. This means that S is not an rds, a
contradiction.

Since neither of the cases holds, then v ∈ S. Therefore, every leaf vertex of G must be
in S.

Theorem 3. Let G = (V,E) be any graph of order n. Then γra(G) = 1 if and only if G
is a trivial graph.



L. Consistente, I. Cabahug, Jr. / Eur. J. Pure Appl. Math, 17 (3) (2024), 2196-2209 2200

Proof. Let γra(G) = 1. By Theorem 1 with n = 1, a graph containing a single vertex,
trivial graph, is an rgda. If G is a trivial graph, then γra(G) = 1. So, G can be a trivial
graph.

Now, assume that G can also be a nontrivial graph with order n ≥ 2. Then there must
exist a singleton set {a} ⊂ V that is an rgda in G. Observe,

Case 1 : G has order n = 2. Then ⟨V ∖ {a}⟩ is an isolated vertex. So, {a} is not an rds,
a contradiction.

Case 2 : G has an order n ≥ 3. Then, knowing that G must be a ds, for every a ∈ {a}
implies

|N [a] ∩ {a}| = |{a}| = 1 ̸≥ n− 1 = |V ∖ {a}| = |N(a) ∩ (V ∖ {a})|.

So, {a} is not a da, a contradiction.

Since neither of the cases holds, G cannot be a nontrivial graph. Therefore, G must
be a trivial graph.

Conversely, let G = (V,E) be a trivial graph. By Theorem 1, V is an rgda in G.
Since an empty set of G cannot dominate G, then V must be the minimum rgda in G.
Therefore, γra(G) = |V | = 1.

Theorem 4. Let G = (V,E) be a graph with isolated vertices and S ⊆ V be any restrained
global defensive alliance in G. If v is an isolated vertex in G, then v ∈ S.

Proof. Let S be an rgda in G = (V,E) and v ∈ G be an isolated vertex. Assume that
v /∈ S. Then ⟨V ∖ S⟩ contains an isolated vertex v. This means that S is not an rds, a
contradiction. Hence, v ∈ S.

Corollary 1. Let En = (V,E) be an empty graph of order n ≥ 1. Then, γra(En) = n.

Theorem 5. If G = (V,E) is any graph with restrained global defensive alliance S, then
1 ≤ |S| ≤ n.

Proof. Let S be an rgda in G = (V,E). By Theorem 1, γra(G) ≤ n. This means that
|S| ≤ n. Since S is necessarily a nonempty set, then |S| ≥ 1. Therefore, 1 ≤ |S| ≤ n.

Theorem 6. Let Kn = (V,E) be a complete graph of order n ≥ 4. Then S ⊆ V is a
restrained global defensive alliance if and only if the following holds:

i. |S| ≥
⌈
n
2

⌉
;

ii. |S| ≠ n− 1.

Proof. Let S be an rgda in Kn = (V,E) of order n ≥ 4. Assume that S does not
satisfy i and ii. This means that either |S| ̸≥

⌈
n
2

⌉
or |S| = n− 1.



L. Consistente, I. Cabahug, Jr. / Eur. J. Pure Appl. Math, 17 (3) (2024), 2196-2209 2201

Case 1 : Suppose that |S| ̸≥
⌈
n
2

⌉
. Since S is an rgda and at least one vertex is necessary

to dominate Kn, S must not be empty. Then for every v ∈ S implies

|N [v] ∩ S| = |S| ̸≥
⌈n
2

⌉
≤ |V | − |S| = |N(v) ∩ (V ∖ S)|.

So, S is not a da, a contradiction. Therefore, |S| ≥
⌈
n
2

⌉
. This proves i.

Case 2 : Suppose that |S| = n − 1. Then there exists a unique vertex a ∈ V such that
a /∈ S. This means that a is not adjacent to another vertex in V ∖ S. So, S is
not an rds, a contradiction. Hence, |S| ≠ n− 1. This proves ii.

Hence, i and ii must be true.
Conversely, let S ⊆ V be a set in Kn = (V,E), of order n ≥ 4, that satisfies i and ii.

By i, S is, necessarily, a nonempty set and for every v ∈ S,

|N [v] ∩ S| = |S| ≥
⌈n
2

⌉
≥ n−

⌈n
2

⌉
≥ |V ∖ S| = |N [v] ∩ (V ∖ S)|.

So, S is a da. Since every vertex in Kn is adjacent to one another, S is also a ds. By ii,
⟨V ∖ S⟩ does not contain an isolated vertex. Hence, S is an rds. Therefore, S is an rgda
in Kn.

Corollary 2. Let Kn = (V,E) be a complete graph of order n ≥ 1. Then

γra(Kn) =

{
|V | if n = 1, 2, 3 ;⌈
n
2

⌉
if n ≥ 4.

(1)

Proof. Let S be an rgda in Kn = (V,E) with order n ≥ 1.

Case 1 : n = 1, 2, 3.

Subcase 1 : n = 1. By Theorem 1, V is an rgda inK1. SinceK1 has only one vertex,
then V is the minimum rgda in K1. Therefore, γra(K1) = |V | = 1.

Subcase 2 : n = 2. Notice that every vertex in V is a leaf vertex. By Theorem 2,
V ∈ S. So, γra(K2) = |V | = 2.

Subcase 3 : n = 3.

If S is a singleton set, say, S = {a} where a ∈ V , then
|N [a] ∩ S| = |{a}| = 1 ̸≥ 2 = |{V ∖ {a}}| = |N(a) ∩ (V ∖ S)|. So, S is
not a da, a contradiction. Hence, S ̸= {a}.
If S has two vertices, say S = {a, b} where a, b ∈ V , then ⟨V ∖ S⟩ con-
tains an isolated vertex c ∈ V ∖S. So, S is not an rds, a contradiction.
Hence, S ̸= {a, b}.
If S = V , then by Theorem 1, V is an rgda in K3.

Now, since S = V is the only rgda in K3, it is also the minimum rgda
in K3. Hence, γra(K3) = |S| = |V | = 3.



L. Consistente, I. Cabahug, Jr. / Eur. J. Pure Appl. Math, 17 (3) (2024), 2196-2209 2202

Case 2 : v ≥ 4. By Theorem 6(i), |S| ≥
⌈
n
2

⌉
. This implies that the smallest value for |S|

is
⌈
n
2

⌉
. Therefore, γra(Kn) =

⌈
n
2

⌉
.

Theorem 7. Let Km,n = (V,E) be a complete bipartite graph with partite sets A1 and
A2 such that |A1| = m and |A2| = n where m,n ≥ 2. Then S ⊆ V is a restrained global
defensive alliance if and only if the following holds:

i. |S ∩A1| ≥
⌊
m
2

⌋
and |S ∩A2| ≥

⌊
n
2

⌋
;

ii. |S ∩A1| = m if and only if |S ∩A2| = n.

Proof. Let S be a rgda in Km,n = (V,E). Suppose that i and ii are false. Then either
i or ii is not true.

Case 1 : i is false. Then either |S ∩ A1| ̸≥
⌊
m
2

⌋
or |S ∩ A2| ̸≥

⌊
n
2

⌋
. Observe the following

subcases:

Subcase 1 : |S ∩A1| ̸≥
⌊
m
2

⌋
.

Since S is an rgda, at least one vertex in A2 must exist to dominate all
vertices in A1. The same is true for the other partite set. So, |S ∩ A1|
and |S ∩A2| are both nonempty. Then for every v ∈ S ∩A2,

|N [v] ∩ S| = |S ∩A1|+ |{v}|
= |S ∩A1|+ 1

̸≥ m− |S ∩A1|
= |A1 ∖ S|
= |N(v) ∩ V ∖ S|.

So, S is not a da, a contradiction. Hence, |S ∩A1| ≥
⌊
m
2

⌋
.

Subcase 2 : |S ∩A2| ̸≥
⌊
n
2

⌋
.

Using similar argument as Subcase 1, it follows that |S ∩A2| ≥
⌊
n
2

⌋
.

Therefore, |S ∩A1| ≥
⌊
m
2

⌋
and |S ∩A2| ≥

⌊
n
2

⌋
. This proves i.

Case 2 : ii is false. Then either |S ∩ A1| = m and |S ∩ A2| ≠ n or |S ∩ A2| = n and
|S ∩A2| ≠ m.

Subcase 1 : |S ∩A1| = m and |S ∩A2| ≠ n.
This means that A1∖S ⊆ V ∖S is empty and A2∖S ⊆ V ∖S is nonempty.
Since every vertex in A2 is only adjacent to vertices in A1, then every vertex
v ∈ A2 ∖ S ⊆ V ∖ S is not adjacent to another vertex in V ∖ S. Hence, S
is not an rds, a contradiction.



L. Consistente, I. Cabahug, Jr. / Eur. J. Pure Appl. Math, 17 (3) (2024), 2196-2209 2203

Subcase 2 : |S ∩A2| = n and |S ∩A1| ≠ m.
Since A1 and A2 are arbitrary, similar argument as Subcase 1 holds.

Therefore, |S ∩A1| = m if and only if |S ∩A2| = n. This proves ii.
Conversely, let S ⊆ V be a set in Km,n = (V,E) where m,n ≥ 2 that satisfies i and ii.

By i, |S ∩A1| ≥
⌊
2
2

⌋
= 1 and |S ∩A2| ≥

⌊
2
2

⌋
= 1, so, S is nonempty and a ds. Moreover,

for every v ∈ S ∩A1,

|N [v] ∩ S| = |A2 ∩ S|+ |{v}| ≥
⌊n
2

⌋
+ 1 ≥ n−

⌊n
2

⌋
≥ |A2 ∖ S| = |N(v) ∩ (V ∖ S)|.

On the other hand, for every w ∈ S ∩A2,

|N [w] ∩ S| = |A1 ∩ S|+ |{w}| ≥
⌊m
2

⌋
+ 1 ≥ m−

⌊m
2

⌋
≥ |A1 ∖ S| = |N(w) ∩ (V ∖ S)|.

This means that S is a da in Km,n. By i and ii, it is guaranteed that whenever A1 ∖ S is
nonempty, A2 ∖ S is also nonempty. Since every vertex in A1 is adjacent to A2, then S is
an rds. Therefore, S is a rgds in Km,n.

Corollary 3. Let Km,n = (V,E) be a complete bipartite graph. If m,n ≥ 2, then
γra(Km,n) =

⌊
m
2

⌋
+
⌊
n
2

⌋
.

Proof. Let S be an rgda in Km,n = (V,E) where m,n ≥ 2, and A1 and A2 be its
partite sets such that |A1| = m and |A2| = n. By Theorem 7(i), |S ∩ A1| ≥

⌊
m
2

⌋
and

|S ∩ A2| ≥
⌊
n
2

⌋
. Now, if X1 ⊆ S ∩ A1 such that |X1| =

⌊
m
2

⌋
and X2 ⊆ S ∩ A2 such that

|X2| =
⌊
n
2

⌋
, then X1 ∪X2 = X ⊆ S is the minimum restrained global defensive alliance

in Km,n. Therefore,

γra(Km,n) = |X| = |X1|+ |X2| =
⌊m
2

⌋
+
⌊n
2

⌋
.

Theorem 8. (Path Graph) Let Pn = (V,E) be a path graph with n ≥ 2. Then S ⊆ V is
a restrained global defensive alliance if and only if the following holds:

i. the leaf vertices of Pn are in S;

ii. ⟨S⟩ has no isolated vertices that are not leaf vertices of Pn;

iii. ⟨V ∖ S⟩, where S ⊂ V , forms a class of P2.

Proof. Let S be an rgda in Pn = (V,E) with n ≥ 2. Suppose that i, ii, and iii are
false. Then either i, ii or iii is not true. Observe the following cases.

Case 1 : i is false.
It is known that Pn has leaf vertices. By Theorem 2, every leaf vertex must be
in S. Hence, the leaf vertices of Pn must be in S. This proves i.



L. Consistente, I. Cabahug, Jr. / Eur. J. Pure Appl. Math, 17 (3) (2024), 2196-2209 2204

Case 2 : ii is false.
Then ⟨S⟩ has atleast one isolated vertex v that is not a leaf vertex of Pn. This
implies that v is adjacent to two vertices w, x ∈ V ∖ S. So,

|N [v] ∩ S| = |{v}| = 1 ̸≥ 2 = |{w, x}| = |N(v) ∩ (V ∖ S)|.

Hence, S is not a da, a contradiction. Thus, ⟨S⟩ has no isolated vertices that are
not leaf vertices of Pn. This proves ii.

Case 3 : iii is false.
Then S ⊂ V and ⟨V ∖ S⟩ does not form a class of P2. This implies that there
exists a component in ⟨V ∖ S⟩ that is not P2. Observe the following cases:

Subcase 1 : If ⟨V ∖ S⟩ has a component P1, then S is not an rds, a contradiction.

Subcase 2 : If ⟨V ∖ S⟩ has a component Pt where 3 ≤ t ≤ n, then S can only dominate
the leaf vertices of Pt. This means that S is not a ds, a contradiction.

Hence, ⟨V ∖ S⟩ forms a class of P2. This proves iii.

Conversely, let S ⊆ V be a set in Pn = (V,E), with n ≥ 2 that satisfies i, ii, and iii.
Since Pn contains leaf vertices, by i, S is a nonempty set. By i and iii, the leaf vertices of
Pn are in S and ⟨V ∖ S⟩ form a class of P2. This implies that every vertex v ∈ V ∖ S is
adjacent to a vertex in S and another vertex in V ∖ S. Hence, S is an rds. In Pn, every
vertex in V is adjacent to at most two vertices. So, by i and ii, for every a ∈ S implies
the following:

Case 1 : a is a leaf vertex

Subcase 1 : a is adjacent to another vertex in S.
Then |N [a] ∩ S| = 2 ≥ 0 = |N(a) ∩ (V ∖ S)|.

Subcase 2 : a is not adjacent to another vertex in S.
Then |N [a] ∩ S| = 1 ≥ 1 = |N(a) ∩ (V ∖ S)|.

Case 2 : a is not a leaf vertex

Subcase 1 : a is adjacent to one vertex in S.
Then |N [a] ∩ S| = 2 ≥ 1 = |N(a) ∩ (V ∖ S)|.

Subcase 2 : a is adjacent to two vertices in S.
Then |N [a] ∩ S| = 3 ≥ 0 = |N(a) ∩ (V ∖ S)|.

These implies that S is a da. Therefore, by i, ii, and iii, S is an rgda in Pn.

Lemma 1. Let Pn = (V,E), n ≡ 0 (mod 4), be a path graph of order n ≥ 2. Then
S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−5, vn−4} is a minimum restrained global defensive
alliance in Pn.



L. Consistente, I. Cabahug, Jr. / Eur. J. Pure Appl. Math, 17 (3) (2024), 2196-2209 2205

Proof. Let S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−5, vn−4}. Notice that all the leaf
vertices of Pn are in S, that is, v0, vn−1 ∈ S. So, Theorem 8 (i) is satisfied. Additionally,
⟨{v3, v4, v7, v8, . . . , vn−5, vn−4}⟩ has no isolated vertices, so ⟨S⟩ has no isolated vertices that
are not leaf. This means that Theorem 8 (ii) is satisfied. Moreover,
⟨V ∖ S⟩ = ⟨{v1, v2, v5, v6, . . . , vn−3, vn−2}⟩ forms a class of P2, hence, Theorem 8 (iii) is
satisfied. This means that, by Theorem 8, S is an rgda in Pn.

Now, suppose that W ⊂ S. Then there exists a vertex in S that is not in W . This
leads to the following cases:

Case 1 : atleast one vertex in {v0, vn−1} is not in W .
Then Theorem 8 (i) is not satisfied, so W is not an rgda in Pn.

Case 2 : atleast one vertex in {v3, v4, v7, v8, . . . , vn−5, vn−4} is not in W .
Then there exists a class in ⟨V ∖ W ⟩ that is not P2, so Theorem 8 (iii) is not
satisfied. Hence, W is not an rgda in Pn.

Therefore, S is a minimum rgda in Pn.

Lemma 2. Let Pn = (V,E), n ≡ 1 (mod 4), be a path graph of order n ≥ 2. Then
S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−6, vn−5} ∪ {vn−2} is a minimum restrained global
defensive alliance in Pn.

Proof. Let S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−6, vn−5} ∪ {vn−2}. Notice that all
the leaf vertices of Pn are in S, that is, v0, vn−1 ∈ S. So, Theorem 8 (i) is satisfied.
Additionally, ⟨{v3, v4, v7, v8, . . . , vn−6, vn−5}⟩ has no isolated vertices and vn−2 is adjacent
to vn−1, so ⟨S⟩ has no isolated vertices that are not leaf. This means that Theorem 8
(ii) is satisfied. Moreover, ⟨V ∖ S⟩ = ⟨{v1, v2, v5, v6, . . . , vn−4, vn−3}⟩ forms a class of P2,
hence, Theorem 8 (iii) is satisfied. This means that, by Theorem 8, S is an rgda in Pn.

Now, suppose that W ⊂ S. Then there exists a vertex in S that is not in W . This
leads to the following cases:

Case 1 : atleast one vertex in {v0, vn−1} is not in W .
Then Theorem 8 (i) is not satisfied, so W is not an rgda in Pn.

Case 2 : atleast one vertex in {v3, v4, v7, v8, . . . , vn−6, vn−5} ∪ {vn−2} is not in W .
Then there exists a class in ⟨V ∖ S⟩ that is not P2, so Theorem 8 (iii) is not
satisfied. Hence, W is not an rgda in Pn.

Therefore, S is a minimum rgda in Pn.

Lemma 3. Let Pn = (V,E), n ≡ 2 (mod 4), be a path graph of order n ≥ 2. Then
S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−3, vn−2} is a minimum restrained global defensive
alliance in Pn.



L. Consistente, I. Cabahug, Jr. / Eur. J. Pure Appl. Math, 17 (3) (2024), 2196-2209 2206

Proof. Let S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−3, vn−2}. Notice that all the leaf
vertices of Pn are in S, that is, v0, vn−1 ∈ S. So, Theorem 8 (i) is satisfied. Additionally,
⟨{v3, v4, v7, v8, . . . , vn−3, vn−2}}⟩ has no isolated vertices, so ⟨S⟩ has no isolated vertices
that are not leaf. This means that Theorem 8 (ii) is satisfied. Moreover,
⟨V ∖ S⟩ = ⟨{v1, v2, v5, v6, . . . , vn−5, vn−4}⟩ forms a class of P2, hence, Theorem 8 (iii) is
satisfied. This means that, by Theorem 8, S is an rgda in Pn.

Now, suppose that W ⊂ S. Then there exists a vertex in S that is not in W . This
leads to the following cases:

Case 1 : atleast one vertex in {v0, vn−1} is not in W .
Then Theorem 8 (i) is not satisfied, so W is not an rgda in Pn.

Case 2 : atleast one vertex in {v3, v4, v7, v8, . . . , vn−3, vn−2} is not in W .
Then there exists a class in ⟨V ∖ S⟩ that is not P2, so Theorem 8 (iii) is not
satisfied. Hence, W is not an rgda in Pn.

Therefore, S is a minimum rgda in Pn.

Lemma 4. Let Pn = (V,E), n ≡ 3 (mod 4), be a path graph of order n ≥ 2. Then
S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−4, vn−3} ∪ {vn−2} is a minimum restrained global
defensive alliance in Pn.

Proof. Let S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−4, vn−3} ∪ {vn−2}. Notice that all
the leaf vertices of Pn are in S, that is, v0, vn−1 ∈ S. So, Theorem 8 (i) is satisfied.
Additionally, ⟨{v3, v4, v7, v8, . . . , vn−4, vn−3}⟩ has no isolated vertices and vn−2 is adjacent
to vn−1, so ⟨S⟩ has no isolated vertices that are not leaf. This means that Theorem 8
(ii) is satisfied. Moreover, ⟨V ∖ S⟩ = ⟨{v1, v2, v5, v6, . . . , vn−6, vn−5}⟩ forms a class of P2,
hence, Theorem 8 (iii) is satisfied. This means that, by Theorem 8, S is an rgda in Pn.

Now, suppose that W ⊂ S. Then there exists a vertex in S that is not in W . This
leads to the following cases:

Case 1 : atleast one vertex in {v0, vn−1} is not in W .
Then Theorem 8 (i) is not satisfied, so W is not an rgda in Pn.

Case 2 : atleast one vertex in {v3, v4, v7, v8, . . . , vn−4, vn−3} ∪ {vn−2} is not in W .
Then there exists a class in ⟨V ∖ S⟩ that is not P2, so Theorem 8 (iii) is not
satisfied. Hence, W is not an rgda in Pn.

Therefore, S is a minimum rgda in Pn.

Corollary 4. If Pn = (V,E) is a path graph of order n ≥ 1, then

γra(Pn) =


n
2 n ≡ 0 (mod 4)
n+1
2 n ≡ 1 (mod 4)

n+2
2 n ≡ 2 (mod 4)

n+3
2 n ≡ 3 (mod 4)

(2)

.



L. Consistente, I. Cabahug, Jr. / Eur. J. Pure Appl. Math, 17 (3) (2024), 2196-2209 2207

Proof. Let Pn = (V,E) be a path graph of order n ≥ 2. Observe the following cases:

Case 1 : n ≡ 0 (mod 4) . Let S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−5, vn−4}. By Lemma
1, S is a minimum rgda in Pn. Therefore,

γra(Pn) = |S|
= |{v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−5, vn−4}|

= 2 +
n− 4

2

=
n− 4 + 4

2

=
n

2
.

Case 2 : n ≡ 1 (mod 4) . Let

S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−6, vn−5} ∪ {vn−2}.

By Lemma 2, S is a minimum rgda in Pn. Therefore,

γra(Pn) = |S|
= |{v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−6, vn−5} ∪ {vn−2}|

= 2 +
n− 5

2
+ 1

=
4 + n− 5 + 2

2

=
n+ 1

2
.

Case 3 : n ≡ 2 (mod 4) . Let S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−3, vn−2}. By Lemma
3, S is a minimum rgda in Pn. Therefore,

γra(Pn) = |S|
= |{v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−3, vn−2}|

= 2 +
n− 2

2

=
4 + n− 2

2

=
n+ 2

2
.

Case 4 : n ≡ 3 (mod 4) . Let

S = {v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−4, vn−3} ∪ {vn−2}.



REFERENCES 2208

By Lemma 4, S is a minimum rgda in Pn. Therefore,

γra(Pn) = |S|
= |{v0, vn−1} ∪ {v3, v4, v7, v8, . . . , vn−4, vn−3} ∪ {vn−2}|

= 2 +
n− 3

2
+ 1

=
4 + n− 3 + 2

2

=
n+ 3

2
.

This completes the proof.

Remark 1. If P1 is a path graph of order 1, then γra(P1) = 1.

Acknowledgements

The authors extend their sincere thanks to those who have played a crucial role in the
completion of this study. A special note of appreciation is directed to the Department
of Science and Technology-Science Education Institute Science and Technology Regional
Alliance of Universities for Inclusive National Development (DOST-SEI STRAND) for
their invaluable assistance throughout the research process.

References

[1] R Barbosa, M Dourado, and L Da Silva. Global defensive alliances in the lexicographic
product of paths and cycles. Discrete Applied Mathematics, 283:168–188, 2020.

[2] F Beggas. Decomposition and Domination of Some Graphs. Data Structures and
Algorithms [cs.DS], University Claude Bernard Lyon, 2017.

[3] I Cabahug and R Isla. Global offensive alliances in some special classes of graphs.
The Mindanawan Journal of Mathematics, 2:43–48, 2011.

[4] J Cabulao and R Isla. On connected partial domination in graphs. European Journal
of Pure and Applied Mathematics, 14(4), 2021.

[5] G Chartrand, L Lesniak, and P Zhang. Graphs and Digraphs. Chapman and
Hall/CRC, New York, 2015.

[6] L Consistente and I Cabahug. Hinge total domination in graphs. Asian Research
Journal of Mathematics, 18(9):25–34, 2022.

[7] G Domke, S Hattingh, R Laskar, S Hedetniemi, R Laskar, and L Markus. Restrained
domination in graphs. Discrete Mathematics, 203:61–69, 1999.



REFERENCES 2209

[8] E Enriquez. Fair restrained domination in graphs. International Journal of Mathe-
matics Trends and Technology, 66(1):229–235, 2020.

[9] A Gaikwad and S Maity. Globally minimal defensive alliances. Information Processing
Letters, 177, 2022.

[10] F Harary. Graph Theory. United States of America: Addison-Wesley Publishing
Company,Inc., Canada, 1969.

[11] T Haynes, S Hedetniemi, and M Henning. Global defensive alliances in graphs.
Electronic Journal of Combinatorics, 10, 2003.

[12] P Kristiansen, M Hedetniemi, and S. Hedetniemi. Alliances in graphs. Journal of
Combinatorial Mathematics and Combinatorial Computing, 48:157–177, 2004.

[13] D Mojdeh, I Masoumi, and L Volkmann. Restrained double roman domination of a
graph. RAIRO. Recherche OpeRationnelle, 56(4):2293–2304, 2022.

[14] M Ortega and R Isla. On semitotal k-fair and independent k-fair domination in
graphs. European Journal of Pure and Applied Mathematics, 13(4), 2020.