CHAPTER 1

Introduction

The subject of graph theory had its beginnings in recreational math problems. The
history of graph theory may be specifically traced to 1735, when Leonhard Euler, a
Swiss Mathematician, solved the famous ‘Konigsberg bridge problem’. Some puzzles
and several problems of practical nature have been instrumental in the development
of various topics in graph theory. While the solution of ’Konigsberg problem’ lead
to the development of Eulerian graph theory, the challenging Hamiltonian graph
theory was developed from the ’Around the World’ game of Sir William Hamilton.
The origin of graph theory is well recorded in the historic book by Biggs, Lloyd and
Wilson [9].
In the present century graph theory has grown into one of the most interdisci-
plinary branches in mathematics with a great variety of applications. Graph theory
can be used as a mathematical tool for designing and analyzing communication
networks, social network systems etc. It has wide range of applications in almost all
branches of science, engineering, social sciences and even in linguistics.
Domination is a flourishing area of graph theory. Similar to the development of
other areas of graph theory, the game of chess becomes inspirational for the study of
dominating sets in graphs. Although the mathematical study of dominating sets in

1
 Chapter 1. Introduction

graphs began around 1960 the subject has historical roots dating back to 1862, when
C. F De Jaenisch [44] analyzed the problem of determining the minimum number
of queens which are necessary to cover an n × n chessboard mathematically. This
problem is said to be the origin of the study of dominating sets in graphs.
In 1958, Claude Berge [6] wrote a book on graph theoy, in which he defined for
the first time the concept of domination number of a graph (although he called this
number the ‘coefficient of external stability’). In 1962, Oystein Ore [49] published
his book on graph theory, in which he used, for the first time, the names ‘dominating
set’ and ‘domination number’. He used the notation d(G) for the domination number
of a graph. In 1977, Cockayne and Hedetniemi [17] published a survey of the few
results known at that time about dominating sets in graphs, in which they used the
notation γ(G) for the domination number of a graph, which subsequently became
the accepted notation.
Domination has applications in facility location problems, in problems involving
finding sets of representatives, in land surveying, in monitoring communication or
electrical networks, in modeling biological or social networks etc. Part of what moti-
vates so much research into domination is the multitude of varieties of domination.
Various types of domination are obtained by imposing additional conditions on the
method of domination so as to meet a specific purpose.
This thesis entitled Domination in Graphs and Fuzzy Graphs intends to
make a small contribution to the vast ocean of domination theory in graphs.

1.1 Basic concepts in graph theory

This section handles the basic notations, terminology and definitions relevant to this
work [12, 3, 10].

Definition 1.1.1. [12] A graph G = (V, E) consists of a finite nonempty set V

of objects called vertices together with a set E of unordered pairs of vertices of G
called edges. The edge e = {u, v} is said to join the vertices u and v . We write
e = uv and say that u and v are adjacent vertices; u and e are incident, as are v
and e. If e1 and e2 are distinct edges of G incident with a common vertex, then e1
and e2 are adjacent edges.

A graph is trivial if its vertex set is a singleton and it contains no edges, and
nontrivial otherwise. An edge with identical end points is called a loop. Edges

2
 Chapter 1. Introduction

joining the same pair of vertices are called multiple edges. A graph which has no
loops and multiple edges is called a simple graph. The graphs considered in this
thesis are all simple.

Definition 1.1.2. [12] The number of vertices in G is called the order of G and the
number of edges in G is called the size of G.

Definition 1.1.3. [12] The degree of a vertex v in a graph G is defined to be

the number of edges incident with v and is denoted by d(v). The minimum of
{d(v) : v ∈ V (G)} is denoted by δ and the maximum of {d(v) : v ∈ V (G)} is
denoted by ∆.

A vertex of degree zero is an isolated vertex and a vertex of degree one is a

pendant vertex or a leaf. The edge incident on a pendant vertex is a pendant edge.
Any vertex which is adjacent to a pendant vertex is called a support vertex.

Definition 1.1.4. [12] If G is a graph of order n, then a vertex of degree n − 1 is

called a universal vertex.

Definition 1.1.5. [12] A vertex u is called a neighbor of a vertex v in G, if uv is

an edge of G. The set of all neighbors of v is the open neighborhood of v and is
denoted by N (v); the set N [v] = N (v) ∪ {v} is the closed neighborhood of v in G.

Definition 1.1.6. [12] A graph H is called a subgraph of G if V (H) ⊂ V (G) and

E(H) ⊂ E(G). A subgraph H of a graph G is a proper subgraph of G if either
V (H) ̸= V (G) or E(H) ̸= E(G). A spanning subgraph of G is a subgraph H of G
with V (H) = V (G).

For a set S of vertices of G, the subgraph induced by S is the maximal subgraph

of G with vertex set S and is denoted by ⟨S⟩. Similarly, for a subset E ′ of E(G),
the edge induced subgraph ⟨E ′ ⟩ is the subgraph of G whose vertex set is the set of
ends of edges in E ′ and whose edge set is E ′ .
Let v be a vertex of a graph G and |V (G)| ≥ 2. Then the induced subgraph
⟨V (G) − {v}⟩ is denoted by G − v and it is the subgraph of G obtained by the
removal of v and the edges incident with v. If e ∈ E(G), the spanning subgraph
with edge set E(G) − {e} is denoted by G − e and it is the subgraph of G obtained
by the removal of the edge e.

3
 Chapter 1. Introduction

Definition 1.1.7. [12] A graph G is complete if every pair of distinct vertices of G

are adjacent in G. A complete graph on n vertices is denoted by Kn .

Definition 1.1.8. [12] A graph G is called bipartite if the vertex set V (G) can be
partitioned into two subsets X and Y such that each edge of G has one end in X
and the other end in Y . (X, Y ) is called a partition of G.

Definition 1.1.9. [12] A graph G is said to be complete bipartite if G is simple,

bipartite with bipartition (X, Y ) and each vertex of X is joined to every vertex of
Y . If |X| = m and |Y | = n, then G is denoted by Km,n . The graph K1,n−1 is called
a star.

Definition 1.1.10. [12] The complement of a simple graph G, denoted by Ḡ, is a

simple graph with vertex set V (G) such that two vertices are adjacent in Ḡ if and
only if they are non adjacent in G.

Definition 1.1.11. [12] A walk W in a graph G is a finite, non- empty, alternating

sequence u0 , e1 , u1 , ..., un−1 , en , un of vertices and edges of G, beginning and ending
with vertices, such that ei = ui−1 ui , for 1 ≤ i ≤ n. This walk joins u0 and un , and
may also be denoted (u0 , u1 , u2 , ..., un−1 , un ); it is sometimes called a u0 − un walk.
It is closed if u0 = un and is open otherwise. If all the vertices u0 , u1 , ..., un are
distinct, then W is called a u0 − un path, P . A path on n vertices is denoted by Pn .

Definition 1.1.12. [12] A cycle of length n ≥ 3 in a graph G is a sequence

(u0 , u1 , u2 , ..., un−1 , u0 ) of vertices of G such that for 0 ≤ i ≤ n − 2, the vertices ui
and ui+1 are adjacent, un−1 and u0 are adjacent and u0 , u1 , u2 , ..., un−1 are distinct.
A cycle on n vertices is denoted by Cn .

Definition 1.1.13. [12] Two vertices u and v of G are said to be connected if there
is a (u, v) path between them. A graph G is said to be connected if every pair of
vertices of G are joined by a path. A maximal connected subgraph of G is called a
component of G.

Definition 1.1.14. [12] The distance between two vertices u and v, denoted by
d(u, v), is the length of the shortest path connecting them.

Definition 1.1.15. [12] Let S be a set of vertices in a graph G. The distance of a

vertex v in G from S is defined as d(v, S) = min{d(u, v) : u ∈ S}. If v ∈ S, then
d(v, S) = 0.

4
 Chapter 1. Introduction

Definition 1.1.16. [12] The eccentricity e(v) of a vertex v of a connected graph G

is max{d(u, v) : u ∈ V (G)}. That is, e(v) is the distance between v and a vertex
farthest from v.

Definition 1.1.17. [12] The radius, rad(G), is the minimum eccentricity among
the vertices of G, while the diameter, diam(G), of G is the maximum eccentricity.
Consequently, diameter of G is the greatest distance between any two vertices of G.

A graph G has radius 1 if and only if G contains a universal vertex. A vertex

v is central vertex if e(v) = rad(G) and the center, Cen(G), is the subgraph of G
induced by its central vertices.

Definition 1.1.18. The second neighborhood of a vertex v ∈ V , denoted by N2 (v),

is {u ∈ V : d(u, v) = 2}.

Definition 1.1.19. [10] The Lexicographic product of graphs G1 = (V1 , E1 )

and G2 = (V2 , E2 ) is the graph G1 [G2 ] whose vertex set is V1 × V2 in which
((u1 , v1 ), (u2 , v2 )) is an edge if u1 u2 ∈ E1 or u1 , u2 are equal and v1 v2 ∈ E2 .

Definition 1.1.20. [27]Tensor product or Cross Product of graphs G1 = (V1 , E1 )

and G2 = (V2 , E2 ) is the graph G1 × G2 whose vertex set is V1 × V2 and edge set is
{((u1 , v1 ), (u2 , v2 )) : u1 u2 ∈ E1 and v1 v2 ∈ E2 }.

Definition 1.1.21. [27]The Strong Product or Normal Product of graphs G1 =

(V1 , E1 ) and G2 = (V2 , E2 ) is the graph G1 ⊠ G2 whose vertex set is V1 × V2 in
which (u1 , v1 ) is adjacent to (u2 , v2 ) if and only if either u1 = u2 and v1 v2 ∈ E2 or
u1 u2 ∈ E1 and v1 = v2 or u1 u2 ∈ E1 and v1 v2 ∈ E2 .

Definition 1.1.22. [27]The Cartesian Product G1 2G2 of graphs G1 = (V1 , E1 ) and

G2 = (V2 , E2 ) is the graph with vertex set V1 × V2 in which (u1 , v1 ), (u2 , v2 ) is an
edge if and only if either u1 = u2 and v1 v2 ∈ E2 or u1 u2 ∈ E1 and v1 = v2 .

1.2 Basic concepts in fuzzy graph theory

Azriel Rosenfeld [51] introduced the concept of fuzzy graphs in 1975, which is a
best tool to handle the real-life uncertainties. He described several fuzzy analogues
of graph-theoretic concepts such as paths, cycles, trees and connectedness. Since
then several works were done on fuzzy graphs. In this section we review some basic

5
 Chapter 1. Introduction

definitions and notations of fuzzy graphs. For terminology in fuzzy graphs we refer
to Mordeson and Nair [48].

Definition 1.2.1. [48] Let S be a finite non empty set. A fuzzy subset of S is a
mapping µ : S → [0, 1]. If µ, ν are two fuzzy subsets of S, then

1. µ ⊆ ν if µ(x) ≤ ν(x) for all x ∈ S and

2. µ ⊂ ν if µ(x) ≤ ν(x) for all x ∈ S and there exists at least one x ∈ S such
that µ(x) < ν(x).

Definition 1.2.2. [48] A fuzzy graph G = (V, µ, σ) is a non empty set V together
with a pair of functions µ : V → [0, 1] and σ : V × V :→ [0, 1] such that for all
u, v ∈ V , σ(u, v) ≤ µ(u) ∧ µ(v). µ is called fuzzy vertex set of G and σ is called the
fuzzy edge set of G respectively.

Definition 1.2.3. [48] The order p and size q of a fuzzy graph G = (V, µ, σ) are
defined to be
X X
p= µ(x) and q = σ(x, y)
x∈V (x,y)∈V ×V

Definition 1.2.4. Let G = (V, µ, σ) be a fuzzy graph and S ⊂ V. Then the scalar
P
cardinality of S is defined to be v∈S µ(v) and it is denoted by |S|. Then p denotes
the scalar cardinality of V , also called the order of G.
P
Definition 1.2.5. [48] The degree of a vertex v is defined as d(v) = u̸=v σ(u, v).
The minimum degree of G is δ(G) = ∧{d(v) : v ∈ V } and the maximum degree is
∆(G) = ∨{d(v) : v ∈ V }. A vertex v in a fuzzy graph is called an isolated vertex if
σ(u, v) = 0 for all u ∈ V .

Definition 1.2.6. [48] A path P of length n is a sequence of distinct vertices

u0 , u1 , u2 , ..., un such that σ(ui−1 , ui ) > 0 for i = 1, 2, ..., n. Strength of a path is
the degree of membership of the weakest edge in P . If u0 = un and n ≥ 3, then P is
called a cycle. The strength of a cycle is the strength of the weakest edge in it.

Definition 1.2.7. [48] The strength of connectedness between two vertices u and
v is defined as the maximum of the strengths of all paths between u and v and
is denoted by CON NG (u, v). A fuzzy graph G = (µ, σ) is connected if for every
u, v ∈ V , CON NG (u, v) > 0.

6
 Chapter 1. Introduction

Definition 1.2.8. [48] An edge e = (u, v) of a fuzzy graph is called an effective

edge if σ(u, v) = µ(u) ∧ µ(v). Then u and v are called effective neighbors. The set
of all effective neighbors of u is called effective neighborhood of u and is denoted by
EN (u).

Definition 1.2.9. [48] A fuzzy graph G is said to be complete if σ(u, v) = µ(u)∧µ(v),

for all u, v ∈ V .

1.3 Domination in crisp graphs

The following are some of the fundamental definitions and results pertaining to
domination in crisp graphs.

Definition 1.3.1. [32] Let G = (V, E) be a graph. A subset S of V is called a

dominating set of G if every vertex v ∈ V is either an element of S or is adjacent to
at least one element in S. The minimum cardinality of a dominating set is called the
domination number of G and is denoted by γ(G). A dominating set of minimum
cardinality is called a γ(G)-set of G.

Definition 1.3.2. [32] A dominating set S is a minimal dominating set if no

proper subset of it is a dominating set. The maximum cardinality of a minimal
dominating set is called the upper domination number of G and is denoted by
Γ(G).

Definition 1.3.3. [32] A set S ⊆ V (G) is a total dominating set of G if every

vertex v ∈ V is adjacent to at least one vertex in S. The minimum cardinality of a
total dominating set in a graph G is called its total domination number, denoted
by γt (G). A γt (G)-set is a total dominating set in G of cardinality γt (G).

Figure 1.1

For the graph G in Figure 1.1, {u, w} is a γ(G)-set, {u, v, w} is a γt (G)-set,

{a, b, c, d, e} is a minimal dominating set of maximum cardinality, γ(G) = 2, γt (G) =
3 and Γ(G) = 5.

7
 Chapter 1. Introduction

Definition 1.3.4. [5] A dominating set S is called efficient if every vertex of G is

dominated by exactly one vertex of S, that is, |N [v] ∩ S| = 1 for every v ∈ V (G).

Theorem 1.3.5. [32] For any connected graph G,

l diam(G) + 1 m
≤ γ(G).
3

Definition 1.3.6. [32]A subset S of V is called an independent set of G if no two

vertices of S are adjacent. A dominating set that is also independent is called an
independent dominating set. The minimum cardinality of an independent dominating
set is called the independent domination number of G and is denoted by i(G). The
maximum cardinality of an independent set in G is called the independence number
of G and is denoted by β0 (G).

Definition 1.3.7. [32]Let S be a set of vertices of a graph G and let u ∈ S. We say

that a vertex v is a private neighbor of u (with respect to S) if N [v] ∩ S = {u}. If
N [u] ∩ S = {u}, then u is its own private neighbor. A dominating set S is a minimal
dominating set if and only if every vertex in S has at least one private neighbor.

Definition 1.3.8. [18, 32] A set S of vertices in G is irredundant if every vertex

v ∈ S has at least one private neighbor. An irredundant set S is called a maximal
irredundant set if no proper superset of S is irredundant. The minimum cardinality
of a maximal irredundant set in a graph G is called the irredundance number of G
and is denoted by ir(G). The maximum cardinality of an irredundant set is called
the upper irredundance number of G and is denoted by IR(G).

The six parameters of domination, independence and irredundance are connected

by a chain of inequalities as shown in the following theorem which was first observed
by Cockayne, Hedetniemi and Miller in 1978.

Theorem 1.3.9. [18] For any graph G,

ir(G) ≤ γ(G) ≤ i(G) ≤ β0 (G) ≤ Γ(G) ≤ IR(G).

In 1968, V.G Vizing [55] posed the following conjecture.

Conjecture 1.3.10. [55] For every pair of finite graphs G and H,

γ(G2H) ≥ γ(G)γ(H).

8
 Chapter 1. Introduction

Vizing’s conjecture is the most significant unresolved problem in the field of

domination theory.

In classical domination a vertex in a graph dominates only the vertices in its

immediate neighborhood. But there are situations where a vertex can influence all
vertices within a given distance. This kind of situation is considered in distance
domination [40].

Definition 1.3.11. [31]For an integer k ≥ 1, a set S ⊆ V (G) is a distance-k

dominating set or simply k-dominating set of G if every vertex of V \ S is within
distance k from some vertex of S. Minimum cardinality among all k-dominating
sets of G is called the k-domination number of G and is denoted by γk (G). It can be
observed that γ(G) = γ1 (G). For the graph given in Figure 1.1, {v} is a distance-2
dominating set and γ2 (G) = 1.

In [21] Dankelmann et al. introduce exponential domination which handles the

situations in which the influence of a vertex extends to any arbitrary distance but
decays exponentially with that distance. Here it is considered that the ‘dominating
power’ of a vertex decreases exponentially, by the factor 12 , with distance. There
are two types of exponential domination; porous and non-porous. In non-porous
exponential domination, vertices in an exponential domination set block the influence
of each other. Whereas in porous exponential domination, the influence of exponential
dominating vertices are not blocked.

Definition 1.3.12. [21] Let G be a graph and S ⊆ V (G). For each vertex u ∈ S
¯ v) = d(v,
and for each v ∈ V (G) \ S we define d(u, ¯ u) to be the length of a shortest
path in ⟨V (G) − (S − {u})⟩ if such a path exists, and ∞ otherwise.
For v ∈ V (G)define
 P 1
¯
u∈S 2d(u,v)−1 if v ∈
/S
wS (v) =
 2 if v ∈ S
If wS (v) ≥ 1 for each v ∈ V (G), then S is a non- porous exponential dominating
set. The smallest cardinality of a non- porous exponential dominating set is the
exponential domination number, γe (G).

Definition 1.3.13. [21] Let G be a graph and S a set of vertices of G. For

v ∈ V (G), define w∗ (v) = u∈S 2d(u,v)−1
1
P
. A porous exponential dominating set

9
 Chapter 1. Introduction

(or p-exponential dominating set) of G is a set S ⊆ V (G) with w∗ (v) ≥ 1 for all
v ∈ V . The minimum cardinality of a porous exponential dominating set is the
p-exponential domination number, denoted by γe∗ (G).

Observation 1.3.14. [21] For every graph G, γe∗ (G) ≤ γe (G) ≤ γ(G).

Theorem 1.3.15. [21] For every positive integer n, γe∗ (Pn ) = γe (Pn ) = ⌈ n+1
4
⌉.

Theorem 1.3.16.
 [21] For every integer n ≥ 3,
 2 if n = 4
γe (Cn ) =
 ⌈ n ⌉ if n ̸= 4
4

Motivated by the difficulties to calculate exponential domination number, God-

dard et al. defined [26] disjunctive domination, which keeps the exponential decay
of the influence, but considers only distances one and two into account.

Definition 1.3.17. [26] For a positive integer b, a set S of vertices in a graph

G is a b-disjunctive dominating set, abbreviated bDD-set, in G if every vertex v
not in S is adjacent to a vertex of S or has at least b vertices in S at a distance
2 from it in G. The b-disjunctive domination number of G, denoted by γbd (G), is
the minimum cardinality of a bDD-set in G. The parameter γ1d is the distance-2
domination number.

In the special case when b = 2, we call a 2DD-set simply a disjunctive dominating

set, abbreviated DD-set, and we call the 2-disjunctive domination number, γ2d (G),
simply the disjunctive domination number. A DD-set of cardinality γ2d (G) is called
a γ2d (G)-set [34]. For the rest of this thesis we look solely at the situation where
b = 2.
We say that a vertex v ∈ V is dominated by a set S if v has a neighbor in S.
v ∈ V is disjunctively dominated by a set S if v is at a distance 2 from at least two
vertices of S. Further, if v has a neighbor in S, we say S dominates the vertex v,
while if v is at a distance 2 from at least two vertices of S, we say S disjunctively
dominates the vertex v [36].

Definition 1.3.18. [36] A set of vertices in G is a disjunctive total dominating set,

abbreviated DT D-set, of G if every vertex is adjacent to a vertex of S or has at
least two vertices in S at a distance 2 from it. The disjunctive total domination
number, γtd (G), is the minimum cardinality of a DT D-set in G .

10
 Chapter 1. Introduction

Some fundamental results of disjunctive domination which we will require in

subsequent chapters of the thesis are given below.

Proposition 1.3.19. [26]For any graph G,

1. γ2d (G) ≤ γ(G)

2. γ2d (G) ≥ γe (G)

Proposition 1.3.20. [26]

1. γ2d (G) = n if and only if G = K̄n .

2. γ2d (G) = 1 if and only if γ(G) = 1.

3. γ2d (Kn,m ) = γ(Kn,m ) = 2 for all n, m ≥ 2.

Proposition 1.3.21. [26] For any graph G,

1. if γ(G) = 2, then γ2d (G) = 2

2. if G has diameter at most 2, then γ2d (G) ≤ 2

ln + 1m
Theorem 1.3.22. [26] For every positive integer n, γ2d (Pn ) = .
4

 [26] For every integer n ≥ 3,

Theorem 1.3.23.
 2 if n = 4
d
γ2 (Cn ) = lnm
 if n ̸= 4
4
Theorem 1.3.24. [26] For a two dimensional grid graph G2,m given by P2 2Pm ,
m ≥ 1,
lm + 2m
γ2d (G2,m ) = .
3

1.4 Domination in fuzzy graphs

This section deals with the variants of domination in fuzzy graphs.

Definition 1.4.1. [54] Let G = (V, µ, σ) be a fuzzy graph and u, v ∈ (V, µ). Then
u dominates v in G if σ(u, v) = µ(u) ∧ µ(v). Then v dominates u also. A subset S
of V is called a dominating set in G if for every v ∈
/ S, there exists u ∈ S such that
u dominates v. The minimum scalar cardinality of a dominating set in G is called
the domination number of G and is denoted by γ(G) or γ.

11
 Chapter 1. Introduction

Bhutani and Rosenfeld [8] have introduced the concept of strong edges of a
fuzzy graph . An edge (u, v) is strong if σ(u, v) = CON N (u, v). If edge (u, v) is
strong, then the vertex v is a strong neighbor vertex u.
A Nagoorgani and V.T Chandrasekaran [25] defined that vertex u dominates v,
if (u, v) is a strong edge. A vertex u dominates itself and its strong neighbors. A set
S of vertices of G = (V, µ, σ) is a strong dominating set if every vertex of V (G) − S
is a strong neighbor of some vertex in S. A minimum strong dominating set in a
fuzzy graph G is a strong dominating set of minimum scalar cardinality. The scalar
cardinality of a minimum strong dominating set is called the strong domination
number of G.
O.T Manjusha and M.S Sunitha [46] defined different types of edges, neigh-
borhoods and neighborhood degree of a vertex in a fuzzy graph. In [45] the same
authors defined strong domination in fuzzy graphs using membership values of strong
P
edges. The weight of a strong dominating set S is defined as W (S) = m(u, v),
u∈S
where m(u, v) is the minimum of the membership values of the strong edges incident
on u. The strong domination number is the minimum weight of strong dominating
set of G.
The above definitions of domination in fuzzy graphs do not consider the fuzzy
subsets of the vertex set.
In 1987, Hedetniemi et al. [33] introduced the concept of fractional domination
and fractional domination number in crisp graphs. Properties of minimal dominating
function and fractional domination in graphs was studied by E. J Cockayne et al. in
[14]. A dominating function (DF) of a graph G = (V, E) is a function f : V → [0, 1]
such that
X
f (x) ≥ 1
x∈N [v]

for all v ∈ V , where N [v] is the closed neighborhood of v. A DF f is called minimal

(MDF) if there is no function g : V → [0, 1] such that g < f and g is a DF. For any
DF f , let
X
|f | = f (v)
v∈V

The fractional domination number γf (G) is defined by

γf (G) = min{|f | : f is an MDF of G}.

12
 Chapter 1. Introduction

In [1] the authors defined (r,s)-fuzzy domination in fuzzy graphs as a fuzzy

subset of the vertex set. Let G = (V, µ, σ) be a fuzzy graph. Let r, s ∈ [0, 1] and
r < s. A fuzzy subset µ1 of µ is called an (r, s)-fuzzy dominating set of G if
 X 
µ1 (u) + µ1 (v) ≥ s for all v ∈ V .
σ(u,v)≥r

Several properties of (r, s)-fuzzy domination and related parameters in fuzzy

graphs are studied in [1].

1.5 Background of the work

In this section, we shall provide a brief analysis of literature on the domination
problem both in crisp graphs and fuzzy graphs.

The well-known concept of domination in graphs and related subset problems

is one of the major topics of research in graph theory. It is a is an excellent tool
for studying situations that can be represented by networks in which a vertex can
exert influence on all vertices in its neighborhood. Haynes [Link] [32] provide a great
resource for the fundamentals of domination in graphs. Surveys of a number of
advanced topics in domination are given in [31].
Domination, independence, and irredundance are closely related concepts. There
has been a vast amount of work published in this area due to the richness of mathe-
matical theory and the variety of practical applications of these concepts. Dominating
sets have been first studied by Berge [6], Ore [49] and Cockayne [17, 15], independent
dominating sets have been studied by Berge [7] and Cockayne [16]. The concept of
irredundance set was introduced by Cockayne et al. [18]. Several results on domi-
nation, independence and irredundance are given in [19, 20, 13]. The domination
chain [18], the inequality involving six parameters on domination, independence and
irredundance, has become one of the strongest focal point of research in domination
theory. In chapter five, we established a similar domination chain in fuzzy graphs.

Another active area of research in domination theory is the Vizing’s Conjec-

ture [55] and related problems. Several versions of Vizing’s conjecture for various
domination-type invariants are studied by many researchers. Vizing-like inequality

13
 Chapter 1. Introduction

for other type of graph products also have drawn attention of many mathematicians
[11].

Many domination parameters are formed by combining domination with other

graph theoretical properties. Some of them are defined by imposing conditions on
the dominating set, but conditions can also be placed on the dominated set or the
method of domination. In this thesis we consider the cases where conditions are
imposed on the dominated set. Different variations of the domination parameters
used in this work are all based on the concept of distance of a vertex from the
dominating set.
Meir and Moon [47] introduced the concept of a k-packing and a k-dominating
set (called a ”k-covering” in [47]) in a graph. In 1976 Slater [53, 39] considered
the problem of finding a minimum k-dominating set. Properties of minimum k-
dominating sets are studied in [53]. The concept of distance domination in graphs
find applications in many situations and structures which give rise to graphs. The
concepts of total k-dominating sets and k-independent dominating sets of G are
introduced in [39]. In the literature, independent domination has drawn a lot of
attention. Properties of distance independent sets are studied in [24]. The concept
of k-irredundance was introduced in [29]. Various relations involving distance
domination parameters can be found in [39, 28, 38, 37].
In exponential domination [21], the domination power of a vertex can reach
any arbitrary distance, but it diminishes exponentially as the distance increases.
Exponential domination is the only framework in the literature in which the effect
of an exponential dominating vertex is global with respect to other vertices. Even
concepts such as distance domination [40] appear basically local because they can be
reduced to ordinary domination by considering the proper powers of the underlying
graph. There are only few results on exponential domination. As mentioned in
Henning et al. [41], the global nature of exponential domination makes it more
difficult to study. This might be the reason for the limited number of results on
it. A model like this could be used to analyze information dissemination in social
networks, where the impact of the information reduces every time it is passed on. In
this thesis we introduce another variant of domination that is also global in nature.
Many existing domination-type structures are expensive to implement. Most of

14
 Chapter 1. Introduction

the variations on domination and total domination studied in literature tend to focus
on adding restrictions which in turn increases their implementation costs. Disjunctive
domination, proposed and studied by Goddard et al. [26] is a method for relaxation
of the domination number. This motivated us in the study of disjunctive domination
in graphs. Several properties of disjunctive and total disjunctive domination number
of a graph are given in [35].
Domination in fuzzy graphs was first introduced by A. Somasundaram and S.
Somasundaram [54]. They defined domination in fuzzy graphs using the concept
of effective edge in a fuzzy graph. A. Nagoorgani and V.T Chandrasekaran [25]
defined domination in fuzzy graphs using strong edges. In [45], O.T Manjusha
and M.S. Sunitha defined strong domination in fuzzy graphs using membership
values of strong edges. All these definitions use either the effective or the strong
edges of a fuzzy graph. But there are situations where we need to consider all the
non-zero edges into account, even if they are very small in strength. Further these
definitions of domination in fuzzy graphs do not consider the fuzzy subsets of the
vertex set. But while considering fuzzy graphs and their subset problems it is more
apt to consider fuzzy subsets of the vertex set than their crisp subsets. As far as
we know, (r, s)-fuzzy domination [1] is the only framework in literature where the
authors consider the fuzzy subset of its vertex set. But this definition also does
not take into account all the non- zero edges incident at a vertex. Motivated by
all these, we defined a fuzzy dominating subset of a fuzzy graph as a fuzzy subset
of its vertex set, in which we also considered all the non-zero edges incident at a
vertex. Our definition allows the importance of all the edges incident at a vertex.
Further, in most of the papers, the authors considered domination as a symmetric
relation between two vertices. That is, whenever there is an effective edge (or strong
edge) between two vertices each vertex dominates the other irrespective of their
strength. But in actual situations it is not always possible that a vertex of weaker
potential dominates another with stronger potential. We have taken this also into
consideration while defining fuzzy dominating sets in fuzzy graphs.

1.6 Organization of the thesis

This thesis entitled ’Domination in Graphs and Fuzzy Graphs’ deals with
different distance related domination parameters both in crisp and fuzzy graphs. It

15
 Chapter 1. Introduction

is divided into six chapters. We shall now give a summary of each chapter.
The first chapter is an introduction and contains the basic definitions and
terminology both in crisp and fuzzy graph theory. It also includes the literature on
different domination parameters in both crisp and fuzzy graphs.
The second chapter deals with Disjunctive Domination in Graphs. We attempted
to investigate different properties of disjunctive domination number in Lexicographic,
Tensor, Strong and Cartesian products of crisp graphs. Further we have investigated
disjunctive domination number of some new graphs derived from given graphs. We
also found the disjunctive domination number of some corona related graphs.
In the third chapter we define Efficient Disjunctive Dominating Sets and Nearly
Efficient Disjunctive Dominating Sets in graphs. We have examined their existence
in several graphs especially in two dimensional grid graphs. We proved the existence
of Nearly Efficient Disjunctive Dominating sets in infinite two dimensional grid
graphs.
In Chapter 4, we initiate a study of Strength Based Domination or sb-domination
in graphs. This chapter is a collaboration work of ours with Dr. S. Arumugam,
National Center for Advanced Research in Discrete Mathematics, Kalasalingam
Academy of Research and Education, Anand Nagar, Krishnankoil-626126, Tamilnadu,
India. We present several fundamental results on the new concept.
The fifth chapter deals with domination in fuzzy graphs. We introduce fuzzy
domination in fuzzy graphs and present several basic results of this parameter.
Several parameters arising from this concept are also introduced and studied.
The Sixth chapter is a concluding chapter, consisting of summary and scope for
further studies.
All the graphs considered in this thesis are finite, un-directed and simple. Some
results of this thesis are published in the journals given in page 123 of this thesis.

16