A STUDY ON HAMILTONIAN FUZZY CYCLES

ON K2n+1 FUZZY GRAPH

PROJECT REPORT
Submitted in partial fulfillment of the requirement for the award of the Degree of

MASTER OF SCIENCE
IN
MATHEMATICS

Submitted By
E.CHRISTINA ABIGAIL
(Reg No: C22PG104MAT005)

Semester –IV
April/May-2025
DEPARTMENT OF MATHEMATICS
VYSYA COLLEGE
Recognized under Section 2(f) and 12(B) of the UGC Act, 1956
(Co-Educational Institution)
Affiliated to Periyar University
Salem-636 103
2023 – 2025
 CERTIFICATE

This is to certify that the dissertation entitled “A STUDY ON

HAMILTONIAN FUZZY CYCLES ON K2n+1 FUZZY GRAPH ” Submitted
in partial fulfillment of the requirement of the Degree of Master of Science in
Mathematics to the Periyar University, Salem is a record of bonafide research work
carried out by E.CHRISTINA ABIGAIL under the Supervision and Guidance, that
no part of the award of any Degree, diploma fellowship or other similar title or prizes
and that it has not been published in part or full in any scientific or popular journals
or magazines.

SIGNATURE OF THE GUIDE HEAD OF THE DEPARTMENT

INTERNAL EXAMINER EXTERNAL EXAMINER

PLACE :

DATE :
 TITLE OF THE DISSERTATION

Dissertation submitted in partial fulfillment of the requirement for the Degree

of Master of Science (Mathematics) to Periyar University, Salem-636 011.

TITLE
A STUDY ON HAMILTONIAN FUZZY CYCLES
ON K2n+1 FUZZY GRAPH
By

STUDENT NAME : E.CHRISTINA ABIGAIL

REGISTER NUMBER : C22PG104MAT005

COLLEGE NAME : VYSYA COLLEGE

YEAR : 2020 – 2022

 DECLARATION

I E.CHRISTINA ABIGAIL (Reg .No:C22PG104MAT005), pursuing

M.Sc., (Mathematics) programme in Vysya College, Salem hereby declare that the
project work entitled “A STUDY ON HAMILTONIAN FUZZY CYCLES ON
K2n+1 FUZZY GRAPH” submitted to Periyar University, Salem in partial
fulfillment of the requirements for the award of the Degree of Master of Science in
Mathematics, is a bonafide work done by me, to the best of my knowledge. The
work reported does not form part of any other thesis (or) work on the basis of which
a degree or award was conferred on an earlier occasion.

PLACE : SIGNATURE OF THE

CANDIDATE

DATE :
 ACKNOWLEDGEMENT

I offer my sincere thanks to Almighty GOD for giving me strength and

wisdom to finish this project work successfully.

I sincerely thank Mr. J. RAJENDRA PRASAD, Correspondent and Secretary

of Vysya College, Salem, Dr. P. VENKATESAN M.Sc., PGDCA., Ph.D., Principal
of Vysya College, Salem for providing the assistance for the successful completion
of the project work.

I sincerely thank the Head of the Department of Mathematics, Vysya College,

Salem for providing necessary reference books whenever needed.

I also thank all the Assistant Professors in the Department of Mathematics,

Vysya College, Salem.

Finally, I express my sincere thanks to my parents, friends and sisters for their
affectionate blessings and loving co-operation in all moments of this academic
venture.
 CONTENT

CHAPTER TITLE PAGE NO

INTRODUTION 1

I PRELIMINARIES 3

SEMI GLOBAL DOMINATING SETS IN

II 7
FUZZY GRAPHS

2.1 SEMI GLOBAL DOMINATING SETS IN

8
FUZZY GRAPHS

2.2 SEMI GLOBAL DOMINATING SET OF

15
INTUITIONISTIC OF FUZZY GRAPHS

HAMILTONIAN FUZZY CYCLES ON K2n+1

III 22
FUZZY GRAPH

CONCLUSION 30

BIBLIOGRAPHY 31
CERTIFICATE
TITLE OF THE DISSERTATION
DECLARATION
ACKNOWLEDGEMENT
CONTENT
 CHAPTER – I
PRELIMINARIES
 CHAPTER- II
SEMI GLOBAL DOMINATING
SETS IN FUZZY GRAPHS
 CHAPTER- III
HAMILTONIAN FUZZY CYCLES
ON K2N+1 FUZZY GRAPH
CONCLUSION
BIBLIOGRAPHY
 INTRODUCTION

Fuzzy graph theory is now finding numerous applications modem science

and technology especially in the fields of information theory, neural network, expert
systems and cluster analysis, medical diagnosis, etc. Bhatta Charya has established
some connectivity concepts regarding fuzzy cut nodes and fuzzy bridges. Rosenfeld
has obtained the fuzzy analogues of several basic graph- theoretic concepts like
bridges, paths, cycles, trees, and connectedness and established some of the
properties. The concept of decomposition of graphs into Hamiltonian cycles,
Hamiltonian paths decomposition of regular graphs was introduced by Klas
Markstrom. We introduce the concept of decomposition of Fuzzy graphs. Next, we
discuss the concept of Hamiltonian path & Hamiltonian cycle of fuzzy graphs. Some
important results in cubic fuzzy graph, complement of fuzzy cycles are discussed.

A finite graph G = (V, E) consists of a finite nonempty set of objects,

V = {v1, v2, ...} called vertices and another finite set,

E {e1, e2, ...} of elements called edges such that each edge ek is identified
with an unordered pair {vi, vj} of vertices. An edge associated with a vertex pair {vi,
vi} is called a self- Loop. The number of edges associated with the vertex is the
degree of the vertex, and d(v) denotes the degree of the vertex v. If there is more
than one edge associated with a given pair of vertices, then these edges are called
parallel edges (or) multiple edges.

A graph that has does not have self-loop or parallel edges Acalled a simple
graph. Two vertices are said to be adjacent if they are the en vertices of the same
edge. A finite alternating sequence of vertices and edges (no repetition of edge
allowed) beginning and ending with vertices such that each edge is incident with the
vertices preceding and following it, is called a walk and an open walk in which no
vertex appears more than once, is called a path. A graph said to be connected if there
is at least one path between every pair of vertices in G, otherwise it is called
disconnected. In a connected graph, a vertex whose removal disconnects the graph
is called a cut-vertex.

1
 Rosenfeld considered fuzzy relations on fuzzy sets and developed the theory
of fuzzy graphs in 1975. Rosenfeld has obtained the fuzzy analogues of several basic
graph-theoretic concepts like bridges, paths, cycles, trees and connectedness and
established some of their properties. Later on, several authors Nagoor Gani and
Radha, M.S. Sunitha and Mini Tom were studied about fuzzy graphs. Fuzzy graph
theory is now finding numerous applications in modem science and technology
especially in the fields of information theory, neural networks, expert systems,
cluster analysis, medical diagnosis, control theory etc.

2
 CHAPTER I

PRELIMINARIES

Definition 1.1

A path p in a graph G*: (V, E) is said to be a Hamiltonian path if it covers all

the vertices of G exactly once.

Definition 1.2

A cycle in a graph G*: (V, E) is said to be a Hamiltonian cycle if it covers all

the vertices of G exactly once except the end vertices.

Definition 1.3

A fuzzy graph with S as the underlying set is a pair G: (σ, µ)

where σ: s → [0,1] is a fuzzy subset, µ: S×S → [0,1] is a fuzzy relation on

the fuzzy subset σ, such that µ (x, y) ≤ σ (x) ˄ σ (y) ∀ x, y ∈ S where ˄ stands for
minimum.

The underlying crisp graph of the fuzzy graph G: (σ, µ) is denoted as G*:(V,
E). Where E=V × V.

Definition 1.4

A path P of length 'n’ is a sequence of distinct nodes u 0, u1, u2................ un

such that µ(ui-1, ui) >0, i =1,2, ................n is called a fuzzy path and the degree of a
membership of a weakest arc is defined as its strength.

Definition 1.5

If u0= un and n ≥ 3, then P is called a cycle and cycle P is called a fuzzy cycle
(f-cycle) if it contains more than one weakest arc.

Definition 1.6

In a fuzzy graph G, a fuzzy path P covers all the vertices of G exactly once
than the path is called Hamiltonian fuzzy path.

3
Definition 1.7

In a fuzzy graph G, a fuzzy cycle C covers all the vertices of G exactly once
except the end vertices then the cycle is called Hamiltonian fuzzy cycle.

Definition 1.8

A fuzzy graph G: (σ, µ) is said to be Complete if

µ (x, y) = σ (x) ˄ σ (y) ∀ x & y.

Definition 1.9

The complement of a fuzzy graph is denoted byGc ∶ ( σc , µc ),, were σc = σ and

µc (x, y) = [(x), σ (y)] − µ (x, y).

Definition 1.10

Kn is a complete fuzzy graph with 'n' vertices.

Definition 1.11

A fuzzy graph G is called r-regular if every vertex of G has degree r.

Definition 1.12

A 3-regular fuzzy graph is called cubic fuzzy graph.

Definition 1.13

A fuzzy graph g is called r-regular if every vertex of G has degree r

Definition 1.14

I-factor of a fuzzy graph is a spanning I-regular fuzzy sub graph of G.

Definition 1.15

A fuzzy graph (f-graph) is a triple G: (V, σ, µ) where V the vertex set, σ is a

fuzzy subset of V and µ a fuzzy relation on σ such that µ (u, v) ≤
σ (u)˄ σ (v) ∀ u, v ∈ V.

4
Definition 1.16

A fuzzy graph H: (V, τ, v) is called a partial fuzzy sub graph of G: (V, σ, µ)

if τ (u) ≤ σ (u) ∀ u, v ∈ τ ∗ and v (u, v) ≤ µ (u, v) for all edges (u, v) ∈ v ∗.
In particular, we Cell H: (v, τ, v) a fuzzy Sub – Graph Of G: (V, σ, µ).

Definition 1.17

If (u) = σ (u) ∀ u ∈ τ ∗ and v (u, v) = µ (u, v) ∀ (u, v) ∈ v ∗ and if in

addition τ ∗ = σ ∗, then H is called a spanning fuzzy sub-graph of G.

Definition 1.18

A weakest edge of a fuzzy graph G: (V, σ, µ) is an edge with least membership

value.

Definition 1.19

A path P of length n is a sequence of distinct nodes u0, u1, u2................ un

such that µ(ui-1, ui) >0, i =1, 2, 3, . . . . n and the degree of membership of a
weakest edge in the path is defined as its strength.

Definition 1.20

If u0 = un and n ≥ 3, then P is called a cycle and a cycle P is called a fuzzy

cycle (f-cycle) if it contains more than one weakest edge.

Definition 1.21

The strength of connectedness between two nodes 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 u-v path P is called the strongest u-v path if its strength equals
CON NG (u, v).

Definition 1.22

A fuzzy graph G: (V, σ, u) is connected if for every u, v in σ*,

CON NG (u, v) > 0.Throughout this paper, it is assumed that fuzzy graph G is
connected.

5
Definition 1.23

An edge of a fuzzy graph is called strong if its weight is at least as great as

the strength of connectedness of its end nodes when it is deleted and u-v path is
called a strong path if it contains only strong edges. In a fuzzy graph the strongest
path need not be a strong path and a strong path need not be the strongest path.

Definition 1.24

An edge (u, v) is a fuzzy bridge (f-bridge) of G if deletion of (u, v) reduces

the strength of connectedness between some pair of nodes.

Equivalently, (u, v) is a bridge if and only if there exist x, y such that (u, v)
is an edge on every strongest x-y path.

Definition 1.25

A node is fuzzy cut node (f-cut node) of G is removal of it reduces the

strength of connectedness between some other pair of nodes. Equivalently, wis a
fuzzy cut node if and only if there exist u, v distinct from w such that w is on every
strongest u-v path. A connected fuzzy graph G: (V, σ, µ) is a block if G has no fuzzy
cut node.

6
 CHAPTER II

Introduction

The study of domination was initiated by Ore and Berge. The domination
number and Independent domination number are introduced by Cockayne and
Hedetniemi. Rosenfeld introduced notion of fuzzy graph and several fuzzy Analogs
of the graph theoretic concepts such as path, cycles and connectedness.
Somasundaram and Somasundaram discussed domination in Fuzzy graphs using
effective edges. Independent domination and Irredundant in fuzzy graph using
strong arcs. The concept of Semi global domination in the crisp graphs was
introduced by Siva Rama Raju and Kumar Addagarla.

We introduce new type of fuzzy graphs such as semi complementary fuzzy

graph and semi complete fuzzy graph which are useful in the defense problems and
Bank transactions. Also we discussed the semi global fuzzy domination set and its
number in Fuzzy graphs, which is useful to solve fuzzy Transportation problems in
more efficient way. Some bounds on semi global fuzzy domination number are
established.

Definition 2.1

Let G =(σ , μ) be a fuzzy graph with strong arcs. The set D ⊆V is said to be
Semi global fuzzy domination set (sgfd-set) of G if D is a Dominating set for both
G and 𝐺 𝑆𝐶 . The minimum cardinality of all sgfd-sets of G is called Semi global
fuzzy domination number and is denoted by 𝛾𝑠𝑔 (𝐺). The maximum cardinality of
sgfd-sets is called upper semi global fuzzy domination number and denoted by
𝛤𝑠𝑔 (𝐺)

Definition:2.2

Let G =(σ, μ) be connected strong fuzzy graph . The set D ⊆V is said to be

Global fuzzy domination set (gfd-set) of G if D is a Dominating set for both G and
𝐺 𝐶 . The minimum cardinality of all gfd-sets of G is called Global fuzzy domination
number and is denoted by γg (𝐺). The maximum cardinality of all gfd-sets of G is
called Upper Global fuzzy domination number and denoted by Γg (𝐺).

7
2.1 SEMI GLOBAL DOMINATING SETS IN FUZZY GRAPHS

Theorem 2.1.1

The necessary and sufficient condition for a connected fuzzy graph with
strong arcs to be semi complete fuzzy graph is any pair vertices lie on the same
triangle or lie on two different tangles have a common vertex.

Proof:

Since by the definition of Semi complete fuzzy graph, every pair of vertices
have a common neighbor, that is any pair of vertices lie on the same triangle.

If not, they lie on two different triangles have a common vertex.

Otherwise, we are not getting the common neighbor for some pair of vertices.

Theorem 2.1.2

Let G be the connected fuzzy graph, then GC = GSC if and only if the between
every pair of non-adjacent vertices there must be two strong arcs.

Proof:

Given G is connected fuzzy graph. Since GC and GSC have same vertex set.

And GC = GSC implies µ (u, v) ∈ GC if and only if µ (u, v) also belongs to

GSC .

Semi Global which implies every pair of non-adjacent vertices in G there

must be two strong arcs.

Similarly, let u and v are not adjacent in G with two strong arcs between them
then GC = GSC .

8
Theorem 2.1.3

Let G be semi complete fuzzy graph, Then GC = GSC

Proof:

Given G is semi complete fuzzy graph.

Therefore, between any pair of non-adjacent vertices there must be two

effective edges.

If two vertices are adjacent in G then also there must be a path of two effective
edges between them in G as it is a semi complete fuzzy graph. i.e., GC = GSC .

Theorem 2.1.4

Let G = (σ, µ) be a fuzzy graph with strong arcs and GSC is also connected
fuzzy graph with effective edges then G is isomorphic to underlying cyclic graph.

Proof:

Let uv ∈ E(G) which implies u, v are the vertices of Gand GSC .

Since GSC is connected there is shortest uv path in GSC .

This induces a path P in G.

Now U {uv} is a cycle in G.

Thus, G is cyclic.

Theorem 2.1.5

Let G = (σ, µ) be a connected fuzzy graph. Then 𝐺 ⸦ (GSC ) if and only if

for each uv in G there is w in V such that between the vertices u, w and w, v there
are two strong arcs.

Proof:

Let us assume 𝐺 ⸦ GSC .

Let 𝑢, 𝑣 ∈ 𝐸(𝐺) implies 𝑢, 𝑣 ∈ 𝐸 (GSC )𝑆𝐶

That is, between u and v there is two strong arcs in GSC

9
 which implies there is win 𝑉(𝐺) such that uw, wv are in 𝐸 (GSC ) between
the vertices u, w and w, v there are two strong arcs in G.

Conversely,

Assume 𝑢, 𝑣 ∈ 𝐸 (𝐺 )

Then by our assumption there is w in V such that between the vertices u, w

and w, v there are two strong arcs in G.

=> 𝑢𝑤, 𝑤𝑣 ∈ 𝐸 (GSC ) and further 𝑢𝑣 ∉ 𝐸 (GSC )

That is, between u and v there are two GSC .

=> 𝑢𝑤, 𝑤𝑣 ∈ 𝐸 (GSC )𝑆𝐶

Thus 𝐸(𝐺)⸦ 𝐸 (GSC )𝑆𝐶

Hence 𝐺 ⸦ (GSC )SC .

Proposition 2.1.1

Let G = (σ, µ) be a connected fuzzy graph with vertex set V and S ⸦ V.

Then S is an independent set of G and GSC if and only if for every, v ∈ S,

between u and v there must be at least three strong arcs.

Proof:

Suppose u and v are neighbor in G implies one strong arc between them and

u, v is neighbor in Gsc implies between u and v there must be two strong arcs.

Now S is independent set of G and Gsc gives between u and v there must be
at least three strong arcs.

Theorem 2.1.6

Let G = (σ, µ) be a strong edge fuzzy bipartite graph with two vertex sets X
and Y, then csc is disconnected fuzzy graph and is a union of two components.

Proof:

Since G is strong edge fuzzy bipartite graph then, any vertex in X is neighbor
of any vertex in Y and vice -versa.
10
 Also, between X and Y there are odd number strong arcs.

So, by definition, in csc no vertex of X neighbor of a vertex in Y and vice

versa

And, between any two vertices of X there are even number of strong arcs and
in Y also.

Hence there is a path between the vertices of X and similarly the vertices of
Y in GSC . Thus, GSC is disconnected and has components formed by graph in X and
that of in Y.

Example 2.1.1

Fuzzy Graph G with 5 vertices and 𝐆𝐒𝐂

Here, the sgfd-sets are {V1,V2,V3}, {V1,V3,V4} and { V1,V3, V5}

Therefore, γsg (𝐺) = 0.8 and Γsg (𝐺) = 1.4

Example 2.2.2

Fuzzy Graph (G) with 5 Vertices 𝑮𝑪

Here in 𝐺 𝑐 , 𝜇𝑐 (𝑢, 𝑣) = 𝜎 (𝑢) ˄ 𝜎 (𝑣) − 𝜇(𝑢, 𝑣), for every 𝑢, 𝑣 ∈ 𝑉.

11
 In the above example, gfd-set is {V1, V5}. Therefore, γg (𝐺) = 0.7 =
Γg (𝐺).

Theorem 2.1.7

Let G = (σ, μ) be connected strong fuzzy graph, then

Min{ σ (Vi) + σ (Vj)} ≤ γsg (G) ≤ p, i ≠ j and for every Vi, Vj Є V.

Proof:

We know that Semi global fuzzy dominating set has at least two vertices.

Let {Vi, Vj} are the vertices, then Min{ σ (Vi) + σ (Vj)} = γsg (G)

If the set contains other than

{𝑉𝑖, 𝑉𝑗} 𝑡ℎ𝑒𝑛 𝑀𝑖𝑛{ 𝜎 (𝑉𝑖) + 𝜎 (𝑉𝑗)} < γsg (𝐺), 𝑖 ≠ 𝑗

If the given G is complete fuzzy graph, then sgfd-set contains all the vertices
of the G, that is γsg (𝐺) ≤ 𝑂(𝐺) = 𝑝

We get, 𝑀𝑖𝑛{ 𝜎 (𝑉𝑖) + 𝜎 (𝑉𝑗)} ≤ γsg (𝐺) ≤ 𝑝 = 𝑂(𝐺).

Theorem 2.1.8.

Let G be a semi complete fuzzy graph, Then

γsg (G) ≥ Min{ σ (Vi) + σ (Vj) + σ (Vk)} , i ≠ j ≠ k

Proof:

It is enough to prove sgfd-set contains at least three vertices.

Suppose sgfd-set contains less than three vertices.

We know that sgfd-set not a singleton.

i.e) sgfd-set contains at least two vertices

Let D = { V1, V2} be a sgfd-set in G

Case 1:

<D> is connected in G

12
 Then V1 V2 is an effective edge in G.

By the definition of semi complete, there is a V3 in G

such that < V1V2V3 > is triangle in G,

i.e., D is not a fuzzy domination set in 𝐺 𝑆𝐶 .

Which is contradiction to D is a sgfd-set in G.

Case 2:

<D> is disconnected in G.

Since G is semi complete fuzzy graph, Then there is V3 in G such that V1V3
and V3V2 are the effective edges in G.

Therefore, In 𝐺 𝑆𝐶 , V3is not dominated by a vertex in D.

This implies,

D is not a sgfd-set in G, which is a contradiction. Therefore we get,

γsg (G) ≥ Min{ σ (Vi) + σ (Vj) + σ (Vk)} , i ≠ j ≠ k

for semi complete fuzzy graph.

Theorem 2.1.9

Let G =(σ, μ) be the fuzzy graph with strong arcs .Then,

γsg (G) = 𝑀𝑖𝑛{ 𝜎 (𝑉𝑖) + 𝜎 (𝑉𝑗) } , 𝑖 ≠ 𝑗

if and only if there is an strong arc uv in G such that each vertex in V – {u,
v} is adjacent to u or v but not both.

Proof:

Suppose γsg (G) = 𝑀𝑖𝑛{ 𝜎 (𝑉𝑖) + 𝜎 (𝑉𝑗) } , 𝑖 ≠ 𝑗

We assume D = {u, v} be the sgfd-set in G.

Let<D>is connected in G, then uv is an strong arc in G.

If any vertex w in V-{u,v} is adjacent to both u and v,

Which implies D is not a dominating set for GSC ,

13
 which is a contradiction i.e., strong arc uv in G such that each

vertex in V – {u,v} is adjacent to u or v but not both.

Conversely, each vertex in V – {u,v} is adjacent to u or v but not both, then

γsg (G) = 𝑀𝑖𝑛{ 𝜎 (𝑉𝑖) + 𝜎 (𝑉𝑗) } , 𝑖 ≠ 𝑗

Theorem 2.1.10.

The set D ⊆ V is a sgfd-set in the strong fuzzy graph G if and only if each
vertex in V – D lies on an effective edge whose end vertices are totally dominated
by distinct vertices in D.

Proof:

Let us assume D is a sgfd-set in the strong fuzzy graph G.

Let V1 ∈ {V– D}. Then there exist distinct vertices V2, V3 in D such that
V1V2 in E(G) and V1V3 in E(GSC ),

Since V1V3 is in E(GSC ), there exist V4 in V such that V1V4 and V4V3 are
effective edges in G.

Case 1:

Suppose V4 = V2, Then, V1V 2 and V2V3 are effectives edges in G which
implies V1 lies on the edge V1V4 and V1,V4 are dominated by V2 and V3 respectively
from D – {V1}

and D–{ V1,V 2 }

Case 2:

Suppose V4 ≠ V2, Then < V2V1, V4V3> is path in G which implies V1 lies on
the edge V1V4 and V1,V4 are dominated by V2 and V3 respectively from D- { V1,V4}

i.e., the end points are totally dominated by distinct vertices in D.

Conversely, assume V1 ∈ {V– D}. By our assumption there is an edge V1V 2

in G such that V1V 3, V1V 4 are effective edges in G and {V3, V 4} are in G ( V3 ≠ V
4)

14
 If V3= V2 then < V1 V2 V4> is a path in G and V1 V2 is G, V1 V4 is in GSC .

If V3 ≠V2 then < V3v1,V2 V4> is a path in G,

which implies V1 V3 is in G and V1 V4 is in GSC .

Hence, we have D is sgfd-set in G.

2.2 SEMI GLOBAL DOMINATING SET OF INTUITIONISTIC OF FUZZY

GRAPHS

INTRODUCTION

Atanassov introduced the concept of intuitionistic fuzzy (IF) relations and

intuitionistic fuzzy graphs (IFGs). Research on the theory of intuitionistic fuzzy sets
(IFSs) has been witnessing an exponential growth in Mathematics and its
applications. R. Parvathy and M.G.Karunambigai’s paper introduced the concept of
IFG and analyzed its components. Nagoor Gani, A and Sajitha Begum, S defined
degree, Order and Size in intuitionistic fuzzy graphs and extend the properties. The
concept of Domination in fuzzy graphs is introduced by A. Somasundaram and S.
Somasundaram in the year 1998. Parvathi and Thamizhendhi introduced the
concepts of domination number in Intuitionistic fuzzy graphs.

Domination is active subject in fuzzy graph and Intuitionistic fuzzy graphs,

and has numerous applications to distributed computing, the web graph and adhoc
networks. Study on domination concepts in Intuitionistic fuzzy graphs are more
accurate than fuzzy graphs, which is useful in the traffic density and
telecommunication systems.

Global domination number of a graph is introduced by E. Sampathkumar in

1989. Siva Rama Raju et. al. analyzed the semi global domination in the crisp graph.
In this paper, we introduce new types of IFGs, semi complementary Intuitiontistic
fuzzy graph and semi complete Intuitiontistic fuzzy graph which are useful in the
defence problems and Bank transcations. Also we discussed the semi global
Intuitionistic fuzzy domination set and its number in the IFG, which is useful to
solve Transportation problems in more efficient way. Some bounds on semi global
Intuitionistic fuzzy number are established.

15
Definition 2.2.1:

G = (V, E ) be a connected IFG with effective edges which is said to be semi

complete IFG, if every pair vertices have a common neighbor in G .

Remark:

1. Every Complete IFG is semi complete IFG. But the converse is not true.

2. Every semi complete IFG has cycles.

Theorem 2.2.1

The necessary and sufficient condition for a connected IFG with effective
edges to be semi complete IFG is any pair vertices lie on the same triangle or lie on
two different triangles have a common vertex.

Proof:

Since by the definition of Semi complete IFG, every pair of vertices have a
common neighbor that is any pair of vertices lie on the same triangle.

If not, they lie on two different triangles have a common vertex.

Otherwise, we are not getting the common neighbor for some pair of vertices.

Example 2.2.1:

In Figure, V1, V2 are lie on the same triangle V1V2V3 and so on. But the pair
of vertices V2,V4 are not lie on the same triangle but lie on two different triangles
with common vertices V1,V3.

Theorem 2.2.2:

Let G be the connected IFG with effective edges, Then G𝐶 = G 𝑆𝐶 if and only

16
if between every pair of non-adjacent vertices there must be two effective edges.

Proof:

Given G is connected IFG.

Since G𝐶 and G 𝑆𝐶 have same vertex set we get G𝐶 = G 𝑆𝐶

lmplies uv ∈ G𝐶 if and only if uv also belongs to G 𝑆𝐶 .

Similarly, let u and v are not adjacent in G then there must be two effective
edges between them.

Theorem 2.2.3

Let G be semi complete IFG with effective edges, then G𝐶 = G 𝑆𝐶 .

Proof:

Given G is semi complete IFG.

Therefore between any pair of non adjacent vertices there must be two
effective edges.

If two vertices are adjacent in G then also there must be a path of two effective
edges between them in G as it is a semi complete IFG.

i.e) G𝐶 = G 𝑆𝐶

Theorem 2.2.4

G =(V,E) is IFG with effective edges and Gsc is also connected with effective
edges then G is cyclic IFG.

Proof:

Let 𝑒 = 𝑢𝑣 ∈ 𝐸(𝐺).

which implies u, v are the vertices of G and G 𝑆𝐶 .

Since G 𝑆𝐶 is connected there is shortest uv path in G 𝑆𝐶 .

This induces a path P in G.

Now 𝑃 ∪ {𝑒} is a cycle in G.

17
 Thus G is cyclic IFG.

SEMI GLOBAL INTUITIONISTIC FUZZY DOMINATION SET OF IFG

(SGIFD-SET)

Theorem 2.2.5

Let G = (V, E) be connected IFG with effective edges, then,

Min {|V𝑖 | + |V𝑗 | < γ𝑠𝑔 (G) ≤ p}. i = j and for every V𝑖 , V𝑗 ϵ V.

Proof:

We know that Semi global Intuitionist fuzzy dominating set has at least two
vertices.

Let {V𝑖 , V𝑗 } are the vertices, then Min {|V𝑖 | + |V𝑗 | = γ𝑠𝑔 (G).

If the set contains other than {V𝑖 , V𝑗 }then ,

Min {|V𝑖 | + |V𝑗 | < γ𝑠𝑔 (G) ≤ p}. i = j.

If the given G is complete IFG then sgifd-set contains all the vertices of the
G, that is γ𝑠𝑔 (G) < 𝑂 (𝐺) = 𝑝

(i.e.) We get, Min {|V𝑖 | + |V𝑗 | < γ𝑠𝑔 (G) ≤ p}.

Theorem 2.2.6

Let G be a semi complete IFG, Then γ𝑠𝑔 (G) ≥ Min {|V𝑖 | + |V𝑗 |, i ≠ j ≠ k

Proof:

It is enough to prove sgifd-set containing at least three vertices.

Suppose sgifd-set contains less than three vertices.

We know that sgifd-set not a singleton.

i.e.) sgifd-set contains at least two vertices.

Let D = { V1, V2 }be a sgifd-set in G.

18
Case 1

<D> is connected in G

Then V1, V2 is an effective edge in G. ··

By the definition of semi complete IFG, there is a V3 in G such that

< V1, V2 V3> is triangle in G,

(i.e.) D is not an Intuitionistic fuzzy domination set in G 𝑆𝐶 .

Which is contradiction to D is a sgifd-set in G.

Case 2

<D> is disconnected in G.

(i.e.) There is no effective edge between V1 and V2.

Since G is semi complete IFG, there is V3 in G such that

V1 V3 and V3 V2 are the effective edges in G.

Therefore, in G 𝑆𝐶 , V3 is not dominated by a vertex in D.

Which implies, dis not a sgifd-set in G

Which is contradiction to our assumption, therefore we get, is

γ𝑠𝑔 (G) ≥ Min {|V𝑖 | + |V𝑗 |, i ≠ j ≠ k

for semi complete IFG.

Theorem 2.2.7

Let G = (V, E) be the IFG with effective edges.

γ𝑠𝑔 (G) = Min {|V𝑖 | + |V𝑗 |}, i ≠ j. If and only if there is an effective edge uv in G
such that each vertex in V - {u, v} is adjacent to u or v but not both.

Proof:

Suppose γ𝑠𝑔 (G) = Min {|V𝑖 | + |V𝑗 |, i ≠ j

We assume D = {u, v} be the sgifd-set in G.

Let <D> is connected in G, then uv is an effective edge in G,

19
 if any vertex winsV - {u, v} is adjacent to both u and v.

Which implies D is not a dominating set for Gsc.

Which is contradiction to our assumption,

(i.e.) effective edge uv in G such that each vertex in V - {u, v} is adjacent to

u or v but not both.

Conversely, each vertex in V - {u, v} is adjacent to u or v but not both, then

γ𝑠𝑔 (G) = Min {|V𝑖 | + |V𝑗 |, i≠j

Theorem 2.2.8

The set D ⸦ V is a sgifd-set in G if and only if each vertex in V- D lies on an

effective edge whose end vertices are totally dominated by distinct vertices in D

Proof:

Let us assume D is a sgifd-set in G Let V1 ∈{V- D}.

Then there exist distinct vertices V2, V3 in D such that

V1 V2 in E(G) and V1V3 in E(GSC),

Since, the edge V2 V3 is in E(GSC),

then there exist V4 in V such that V1 V4 and V4 V3 are effective edges in G.

Case 1

Suppose V4= V2, Then, V1V2 and V2V3 are effectives edges in G.

which implies V1 lies on the edge V1 V4 and V1, V4 are dominated by V2 and
V3 respectively from D - {V1}, D - {V1 V2}.

Case 2

Suppose V4= V2

Then < V2 V1 V2 V2V3 >is a path in G which implies V1 lies on the edge V1
and V3, V4 are dominated by V2 and V3 respectively from D - { V1,V4}

(i.e.) each vertex in V-D lies an effective edge whose end vertices are totally

20
dominated by distinct vertices in D.

Conversely,

Assume V1 ∈ {V-D}. By our assumption there is an edge V1 V2 in G such that

V1 V3, V2 V4 are effective edges in G and { V3, V4}are in G (V3= V4)

Now, If V3= V2 then < V1 V2 V4>is a path in G and V1 V2 is in G,

but V1 V4 is in G 𝑆𝐶 And, If V3 -=I=- V2 then

< V3 V1 V2 V4> is a path in G, which implies V1 V3is in G and V1 V4is in G 𝑆𝐶 .

Hence, we have D is sgifd-set in G.

21
 CHAPTER III

HAMILTONIAN FUZZY CYCLES ON K2n+1 FUZZY GRAPH

Introduction

Fuzzy graph theory is now finding numerous applications modern science

and technology especially in the fields of information theory, neural network, expert
systems and cluster analysis, medical diagnosis, etc. Bhatta Charya has established
some connectivity concepts regarding fuzzy cut nodes and fuzzy bridges. Rosenfeld
has obtained the fuzzy analogues of several basic graph- theoretic concepts like
bridges, paths, cycles, trees, and connectedness and established some of the
properties.

The concept of decomposition of graphs into Hamiltonian cycles,

Hamiltonian paths decomposition of regular graphs was introduced by Klas
Markstrom. We introduce the concept of decomposition of Fuzzy graphs. Next we
discuss the concept of Hamiltonian path & Hamiltonian cycle of fuzzy graphs. Some
important results in cubic fuzzy graph, complement of fuzzy cycles are discussed

Definition 3.1

Kn is a complete fuzzy graph with ‘n’ vertices.

Definition 3.2.

A fuzzy graph G is called r – regular if every vertex of G has degree r

Definition 3.3

A 3- regular fuzzy graph is called cubic fuzzy graph.

Definition 3.4.

A fuzzy graph g is called r – regular if every vertex of G has degree r

Definition 3.5

1-factor of a fuzzy graph is a spanning 1- regular fuzzy sub graph of G.

22
Theorem 3.1

For any n≥ 1, K2n+1 fuzzy graph is decomposable into n Hamiltonian fuzzy

cycles C2n+1.

Proof:

Let G =K2n+1 be a fuzzy graph.

Label the vertices 0,1,2,3,….,2n-1.

In this fuzzy graph form the Hamiltonian fuzzy cycles as follows.

(C1) is a fuzzy cycle that is

(C1 ) ∞, 0,2n − 1,1,2n − 2,2,2n − 3, … n − 1, 𝑛, ∞ z

(C2 ) ∞, 1,0,2,2𝑛 − 1,3,2𝑛 − 2, … , 𝑛, 𝑛 + 1, ∞

(C3 )∞, 2,1,3,0,4,2𝑛 − 1, … . . 𝑛 + 1, 𝑛 + 2, ∞

(C𝑛 ) ∞, 𝑛 − 1, 𝑛 − 2, 𝑛, 𝑛 − 3, 𝑛 + 1, 𝑛 − 4, … . .2𝑛 − 2,2𝑛 − 1, ∞

(so each time we add 1 to every label and find the remainder modulo 2n ).

For example, label vertices of K9 with ∞,0,1,2,3,4,5,6,7 (n=4) and decompose

it into

∞ 0 7 1 6 2 5 3 4 ∞

∞ 1 0 2 7 3 6 4 5 ∞

∞ 2 1 3 0 4 7 5 6 ∞

∞ 3 2 4 1 5 0 6 7 ∞

(you can visualize this by putting vertices 0 through 2n-1 clockwise along a circle
with outside with circle.)

Example 3.1

Consider K5 a complete fuzzy graph on five vertices in figure.1, which has

two Hamiltonian fuzzy cycles. Let it be 123451 and 135241. Here the membership
values of each edge are greater than zero and it contains more than one weakest arc.
23
 Fig: K5 Fuzzy graph

Theorem 3.2

For any n≥1, K2n is decomposable into 2n-1 1-factors.

Proof:

Label vertices ∞,0,1,2,… ,2n-2.

start with a 1-factor ∞,0; 1,2n-1; 2,2n-2; . . . n-1,n

use the turning trick to obtain the following decomposition:

∞,0; 1,2n-1; 2,2n-2; . . . n-1,n

∞,1; 2,0; 3,2n-2; . . . n, n+1

∞,2n-2; 0,2n-3; 1,2n-4; . . . n-2,n-1.

Example 3.2

In figure K7 is decomposed into 3C7 .That is three hamiltonian fuzzy cycles.

Lable the vertices clockwise around the circle and always go to the next vertex in
the first copy of the Hamiltonian fuzzy cycle (C7) .

Fig. K7 Fuzzy Graph

24
 We get 12345671, 13572461, 14736251.

We can’t extend this to K9. As it turns out, K9 is decomposable into C9 any

way. We just need a more clever trick called the turning trick.

Corollary 3.1

For any n≥1 ,K2n is decomposable into n Hamiltonian fuzzy paths P2n-1.

Proof:

Take the composition of K2n+1. and

By theroem, delete the vertex. K2n+1 will become K2n,

While each Hamiltonian fuzzy path P2n-1 of K2n

Theorem 3.3

Let G (σ,μ) be a fuzzy graph where G*: (V,E) is an odd cycle.

Then G is regular iff μ is a constant function.

Proof:

If μ is a constant function, say μ(uv)=c,

for all uv∈E, then d(v)=2c, for every v∈V.

So G is regular.

Conversely, suppose that G is a k-regular fuzzy graph.

Let e1,e2,…,e2n+1 be the edges of G* in that order.

Let μ(e1) = k1. Since G is k-regular,

μ(e2) = k-k1

μ(e3) = k-(k-k1)=k1

μ(e4) = k- k1 and so on.

Therefore μ(ei)= k1, if i is odd

= k-k1 if i is even

Hence μ(e1) = μ(e2n+ 1)=k1.

25
 so if e1 and e2n+1 incident at a vertex u ,

then d(u)=k. so d(e1) + d(e2n+1) = k

ie) k 1 + k1 = k

2k1 =k

k1 = k/2.

Hence k-k1 =k/2. so μ(ei) = k/2, for all i.

Hence μ is a constant function.

Example 3.3

In the following example figure is a cubic fuzzy graph.

Fig. Cubic Fuzzy Graph

Theorem 3.4

Let G (σ,μ) be a fuzzy graph where G*: (V,E) is an even cycle. Then G is
regular iff μ is a constant function or alternate edges have same membership
values.

Proof:

If either μ is a constant function or alternate edges have same membership

values, then G is a regular fuzzy graph.

Conversely, Suppose G is a k-regular fuzzy graph. Let e1,e2,…,e2n be the

edges of even cycle G* in that order.

26
 Proceeding as in theorem,

μ(ei) = k1, if i is odd

= k-k1 if i is even

If k1 = k-k1, then μ is a constant function.

If k1≠ k-k1, then alternate edges have same membership values.

Example 3.4

In the following example figure 4 is a 1-regular fuzzy graph.

Fig. I- regular Fuzzy Graph

Theorem 3.5

Let G be a cubic fuzzy graph where G* is a cycle. Then G is a fuzzy cycle. It

cannot be a fuzzy tree.

Proof

Assume that G be a cubic fuzzy graph where G* is a cycle.

That is G be a 3- regular fuzzy graph on a cycle G*, then by theore , either μ

is a constant function or alternate edges have same membership values.

So there does not exist a unique edges xy such that

𝜇(𝑥𝑦) =∧ {𝜇(𝑢𝑣)/ 𝜇(𝑢𝑣) > 0}.

Therefore G is a fuzzy cycle.

Hence by lemma , G cannot be a fuzzy tree.

27
Example 3.6

In the following example figure, G (σ,μ) be a fuzzy graph where G*: (V,E)
is an odd cycle. Also G is regular if μ is a constant function.

Theorem 3.6

Let G :(σ,μ) be a fuzzy graph such that G* is a cycle with more than five
vertices. Then (G*)c cannot be a cycle.

Proof:

Given G* is a cycle having n vertices where n≥6.

Then G* will have exactly n edges.

Since all the vertices of G are also present in G𝐶 .

Therefore number of vertices in G𝐶 is n.

Let the vertices of G and G𝐶 be v1, v2, …,vn..

Then G𝐶 must contain atleast the following edges.

(v1, v3), (v1, v4), (v1, v5), . . . , (v1, vn);

(v2, v4), (v2, v5), . . . . . . . . . ., (v2, vn);

(v3, v5), (v3, v6), . . . . . . . . . ., (v3, vn )

since n≥6 the total number of edges in G* will be greater than n.

Thus G𝐶 will not be a cycle.

28
Example 3.6

In the following example figure is G (σ,μ) be a fuzzy graph where G*: (V,E)
is an even cycle. Also G is regular if μ is a constant function or alternate edges have
same membership values.

29
 CONCLUSION

We discussed Hamiltonian K2n+1 fuzzy cycles on fuzzy graph, semi total

blocks in fuzzy graphs, semi global dominating sets in fuzzy graphs, semi global
dominating set of intuitionist fuzzy graphs.

Next, we have introduced the concept of fuzzy cycle, fuzzy paths in a fuzzy
graph. A complete analysis of Hamiltonian fuzzy cycle in K2n+1 fuzzy graph is
presented. Next, we are studying the properties of regular fuzzy graph and
complement of fuzzy cycles.

We have finally studied some interesting results regarding the semi total
blocks in fuzzy graphs are obtained. Finally, the results are

|𝑬𝑺𝑻𝑩 𝑭(𝑮)| = |𝑬 𝑭 (𝑮) | + | 𝑽 (𝑩𝟏 ) | + |𝑽 (𝑩𝟐 ) | + … . . . | 𝑽 (𝑩𝑲 )|

30
 BIBLIOGRAPHY

[1] A.Nagoor Gani1, S. Yahya Mohamed 2 and R. Jahir Hussain3 Intern. J

Fuzzy Mathematical Archive Vol. 4, No. 2, 2014, 115-122

[2] A.Nagoor Gani and V.T. Chandrasekaran, Domination in fuzzy graph,

Advances in Fuzzy Sets and Systems, 1(1) (2006) 17-26.

[3] A,Rosenfeld, Fuzzy graphs, in: LA. Zadeh, K.S.Fu, M. Shimura (Eds).

Fuzzy sets and their applications to cognitive and decision processes,

Academic press, New York, 1975 pp, 77-95.

[4] A.Somasundaram and Somasundaram, Domination in fuzzy graphs, Pattern

Recognit. Lett., 19(9) (1998) 787-791.

[5] Bhattacharya. P Some remarks on fuzzy graphs, Pattern Recognition Lett

6(1987) 297- 302.

[6] Bondy J. A. and Murty U.S. R. "Graph Theory with Applications", The

Macmillan Press Ltd, (1976).

[7] Dr. G. Nirmala, Vijaya International Journal of Scientific and Research

Publications, Volume 2, Issue 11, November 2012 1

[8] Frank Harary, Graph theory, Narosa /Addison Wesley. Indian student edition

1988.

[9] Klas Markstrom, even cycle decompositions of 4- Regular graphs and line

graphs.

[10] KR. Bhutani and A. Rosenfeld, Strong arcs in fuzzy graphs, Information

Sciences,152 (2003) 319-322.

[11] L.A. Zadeh, Fuzzy sets, Information control 8 (1965) 338- 353

31
[12] Mohiddin Shaw, B. Narayana, D. Srinivasulu and A. Sudhakaraiah Asian

Journal of Fuzzy and Applied Mathematics, Volume 02 - Issue 01, February

2014

[13] Sunitha M.S., Vijayakumar. A, "Blocks in Fuzzy Graphs", The journal of

fuzzy Mathematics, Vol.13, No. I,13-23.

[14] Siva Rama Raju.S.V., and Kumar Addagarla. R., Semi Global Domination,

International Journal of Mathematical Archieve-3(7), 2012, 2589-2593.

[15] S. Yahya Mohamed and R. Jahir Hussain, IOSR Journal of Mathematics

(IOSR-JM) Volume 10, Issue 4 Ver. II (Jul-Aug. 2014), PP 23-27

32