International Journal of Scientific & Engineering Research, Volume 3, Issue 12, December--2012 1

ISSN 2229-5518

Application of Strong Graphs in Wireless

Networks

Nishad T M
Assistant Professor of Mathematics
MES College of Engineering and Technology
Ernakulam, Kerala, India
Email: wadud400@gmail.com

Abstract— I introduced Strong Graphs in the paper “Strong graphs, its properties and some families of Strong Graphs”on October 2012. In this paper the application of Strong Graphs in wireless networks is discovered.A virtual backbone structure is constructed using Nishads Algorithm.The properties of Nishad Graph and Nishad Algorithm is proved.The performance of Nishads Algorithm is measured.

Keywords— Graph labeling, NG, NSG, Nishads Algorithm,NE,NN, Strong edge, Strong Graphs, SG(r ), Weak edge, Weak graph

1 INTRODUCTION

—————————— • ——————————
n a mobile adhoc network, the nodes can join or leave the connection at any time. As a result connectivity among the mobile nodes becomes a major constraint. Mobility manage- ment is another important problem that needs to be addressed so that the mobile nodes can enjoy their services as they roam
Definition 2.4: Weak Edge
A weak edge of a labeled graph is the edge u-v which is not strong.

Definition 2.5: N Graph

An N Graph is a strong α labeled graph N of | E( N ) |= n with

the following properties.

through the network. Connectivity based on virtual backbone
formation is an effective approach. The objective of the paper
1. Its

n 1 edges have a common vertex u where

is to form an efficient backbone structure based on my pro- posed algorithm (Nishads Algorithm) and to merge the net- work when the node moves thereby maintaining connectivi- ty, ensuring mobility management and parameters like great- er throughput, more packet delivery ratio, less packet drop,

ψ (u) = n

2. The nth edge vv’has α labeling

andψ (v1 ) = n κ ,κ N .

ψ (v) = n 2k

more energy efficient and less delay .The performance of NA is measured and discovered that it is more effective than the existing method TAP.

2 SECTION I: PRELIMINARIES

Definition 2.1: Graph Labeling

A labeling of a Graph G = (V, E) is a one-to-one mapping Ψ
of the vertex set V(G) in to the non negative set of integers that
For the convenience of proving theories, we shall call N graph by the name of the author.i,e, Nishad Graph

Definition 2.6: SG(r )

Definition: Given a set V of nodes distributed on a Eucledian space,The Sphere graph of radius r,denoted by SG( r) is the graph in which edge (u,v) exists if and only if the Euclidian distance between u and v ,i.e, IuvI is atmost r.

Definition 2.7: NSG

induces for each edge{u,v}
vertex labels Ψ (u) and Ψ(v).
Definition 2.2: Strong Graph
E(G) a label depending on the
A Nishad Sphere Graph is a Nishad Graph which satisfies the
the condition the n-1 edges incident to u is such that the euc- ledian distance I u ui I < r, i= 1,2,3,..,n-1 where r=max {Eucli- dian distance I u uiI} and v’ belongs to complement of SG( r).
A labeled graph G=(V,E) is a strong graph if it satisfies the condition that there exist a number δ where 0 < δ < Max {ψ(e)/e
E E(G) and ψ, the labeling} such that Min{ψ(u), ψ(v)}< ψ(uv) < Max {ψ(u), ψ(v)}
Note: 2.2.1: If the labeling is α then Max {ψ(e)/e E E(G)}=
| E(G)| and ψ(uv) = | ψ(v) – ψ(u) |

Definition 2.3: Strong Edge

A strong edge u-v of a strong graph is the edge which satisfies

Min{ψ (u),ψ (v)} < ψ (uv) < Max{ψ (u),ψ (v)}

Definition 2.8: NE

The edge vv’ of NSG, where the nodes v and v’ belong to dis- joint SG is called Nishad Edge (NE)

Definition 2.9: NN

A Nishad Network NN is the network formed by the active links of Nishads Algorithm.
Definition2.10: Weak Graph
An labeled graph is weak if its all edges are weak.

IJSER © 2012 http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 3, Issue 12, December-2012

ISSN 2229-5518 2

3 SECTION II: PROPERTIES OF NISHAD GRAPH

Theorem 3.1:
The minimum number of edges in a Nishad Graph is 3.
Theorem 3.4:
The number of strong edges ina star G obtained by modifying


E(G) such that E(G)= E(N) U {uv’} – {vv’},where N is a Nishad
Proof: is enough to prove that if G is a connected graph with
Graph with

E ( N ) = n

is (n-1)/2 if n is odd and (n/2)-1 if n

E(G) < 3 ,then G fails to become a Nishad Graph. Case 1. E (G) = 1

Let e=uv be the edge.Without loss of generality, the possible

α labeling is ψ (u) = 0 and ψ (v) = 1 .It is obvious that the

edge e is weak. Case 2. E (G) = 2

Let e1=uv, e2=vw be the edges.Without loss of generality three
types of α labeling is possible

2.1 ψ (u) = 0 , ψ (v) = 1 and ψ (w) = 2

2.2 ψ (u) = 0 , ψ (v) = 2 and ψ (w) = 1

2.3 ψ (u) = 1 , ψ (v) = 0 and ψ (w) = 2

It is obvious that all edges are weak.
Theorem 3.2:
Let N be a Nishad Graph ,the star G obtained by modigying E(G) such that E(G)= E(N)U{uv’} – {vv’} is a strong Graph.But its Complement is weak.
Proof: As per definition of Nishad Graph,
is even.Cosequently the number of weak edges of G is
(2n+1)/2 if n is odd and (n/2)+1 if n is even.

Proof: Suppose n is odd.: Let u1, u2, u3,…, un V (G) such thatψ (u) = n, ψ (ui ) {0,1, 2, ..., n 1} .It is clear that n-1

and n+1 are even and the inequality r < n-r <n holds for r =
1,2,3,..,(n-1)/2 and does not holds for r > (n-1)/2.Similarly we shall prove for even n.Since the total number of edges in G is n,The number of weak edges = n- number of strong edges.There fore the number of weak edges =(n+1)/2 if n is odd and (n/2)+1 if n is even.
Theorem 3.5:
Let N be a Nishad Sphere Graph , with IE(N)I >3, the strong
Graph G obtained by modigying E(G) such that E(G)= E(N) –

{vv’} and ψ (u) = n -1 has all its nodes belongs to SG(r).

Proof: To prove that G is strong.Since ψ (u) = n -1, the other

nodes of G can be labeled using the numbers 0,1,2,3,,..n-2.
Since IE(N)I > 3, IE(G)I >2.There fore there exists a strong edge.By the definition of NSG, its clear that n-1 edges incident to u belongs to SG. The edge v’ doesnot belong to SG.So all nodes of G belong to SG.
Theorem 3.6: The inverse of NG is strong but not NG.

ψ (u) = n ,ψ (v) = n 2k

and ψ (v ' ) = n k .Therefore In

Proof: NG is strong by definition.It is proved that the set of
G , n edges incident to u and . Let u1, u2, u3,…, un-1=v, un=v’
be the n vertices which form the edges ei =ui u, i=1,2,3,…,n in

G.Since ψ (u) = n ,ψ (ui ) = n {0,1, 2, ..., n 1} .By proper-

ty 1, n 3 .Therefore there exists k {1, 2,..., n 1} such that

k < n-k < n.
strong Graphs is closed under inversion [1].This implies that

inverse of NG is strong.In the inverse of NG,ψ (u) n .So

inverse of NG is not NG.


Theorem 3.7:
To prove that the complement of G is weak.
The number of strong edges of an NG with

E ( N ) = n is

By the definition of Complement,ψ c (u) = n n = 0 .

(n-1)/2 if n is odd and (n/2)-1 if n is even.Cosequently the




There fore

ψ (ui ) {1, 2,..., n}

for i = 1, 2, 3,..., n

and
number of weak edges of NG is (2n+1)/2 if n is odd and

ei = uui

= ψ (ui ) 0 = ψ (ui ) All edges are weak.

(n/2)+1 if n is even.
Proof: Let n be odd. Let u1, u2, u3,…, un V ( N ) .Without loss
Lemma 3.2.1:

of generality letψ (v ') = n 1

and let other vertices be such
The star G obtained by modigying E(G) such that E(G)=

thatψ (u) = n, ψ (ui ) {0,1, 2,..., n 2} .Note that n 3 by

E(N)U{uv’} – {vv’} ,where N is a Nishad Graph, tends to a non

property 1.Therefore (n 1) / 2 n 2

It is clear that n-1

graceful Graph asψ (u) k ,

k {0,1, 2, 3, ..., n 1} .

and n+1 are even .i.e, the inequality r < n-r <n holds for r =

Proof: Asψ (u) k ,

k {0,1, 2, 3, ..., n 1} ,

1,2,3,..,(n-1)/2 and does not holds for r > (n-1)/2.Similarly we

ψ (ui ) p where p {0,1, 2,..., n} {k}

for i=1, 2,..,n.
shall prove for even n.Since the total number of edges in G is


There fore there exists two numbers Ip+kI and Ip-kI such
n,The number of weak edges = n- number of strong
that ei

= p .So the Graph fails to become Graceful.

edges.There fore the number of weak edges =(n+1)/2 if n is
odd and (n/2)+1 if n is even.
Theorem 3.3:
Every Complete Graph K with

V ( K ) = n,

n 3

Theorem 3.8:
has n stars G obtained by modifying E(G) such that E(G) = E(N) U {uv’} – {vv’} where N is a Nishad Graph.

Proof: Let ui V (K ) ,

NG is Graceful and strong but doesnot belong to any of the
sets Odd Graceful, even Graceful, edge odd graceful and even vertex Graceful.
Proof: As per definition of NG it is Graceful ad strong. And it
Form Gi such

E(Gi ) = {ui v j }

j = 1, 2, 3,..., n and deleting

follows from definition that ψ (u) = n ,ψ (v) = n 2k

and
all other edges of K.Then Gi has the property

ψ (v ' ) = n k ,

where n, k N .Hence it fails to admit the

E(Gi)=E(N)U{uv’} – {vv’} for some Nishad Graph N. Since i=1,2,…,n.There exists n such sub graphs.
conditions required for Odd Graceful, even Graceful, edge
odd graceful and even vertex Graceful.

IJSER © 2012 http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 3, Issue 12, December-2012 3

ISSN 2229-5518

4 SECTION III: APPLICATION IN WIRELESS NETWORKS

Due to more links of root node, its signal strength reduces
Let the total number of nodes in the given network be N.Let r

andψ (u) k ,

k {0,1, 2, 3, ..., n 1} .

be such that every disjoint spheres consists minimum 3 edges inside the SG.Divide the network in to disjoint subnetworks such that each sub network consists nodes having Euclidian distance < r .Consider a subnetwork with ‘n+2’number of nodes and ‘l’ number of links; we construct a complete graph by removing loops and introducing and maintaining one di- rect link between every two nodes.From this a Strong Graph is formed having property 5.Now label the nodes using the numbers {0,1,2,3,…,n} corresponding to the ascending order of energy at the nodes.If two or more nodes have same energy level, then assign consecutive numbers to label the nodes.This is the proposed Nishads Algorithm. Hence forth the network has various strong graph structures ensuring to- pology maintenance. The disjoint SG( r) are connected by NE.
In the first phase the root nodes are selected. The node

Then by Lemma 2.2.1 the graph fails to admit graceful labeling and thus it fails to become a strong Graph.
u corresponding to

ψ (u) = n is selected as the root node.

Active link

From there a one hop distance is maintained to each node.
Thus a strong graph is constructed thereby covering all vertic- es. By strong graph formation the packet can be transferred through energy efficient links and also better throughput can be achieved.By changing r, better parameters can be obtained and the performance of Nishads Algorithm can be improved.
Nishad’s algorithm (NA)
Step 1: Start
Input: Unconnected Network.
Step 2: Form disjoint SG (r) covering all nodes.
Step3: Select one SG( r) and name vertices u0 , u1, u2, u3,…, un
Step 4: Join ui –uj for i= 0,1,2,…,n and j=i+1,i+2,…,n. Step 5: Receive the signal
Step 6:Label the nodes using {0, 1, 2… n} according to the as- cending order of signal strength.
Step 7.1:If two or more nodes have same signal strength, use
consecutive distinct numbers to label the nodes. Step 8: Selection of Root node.

For ψ (u) = n ,Select Root node R= u

Step 9: Make all links’ uui active and all other links inactive. Step10: Check ψ (u) = n in time [0,t].

------------------- Inactive link

Fig.1

Fig.2

Figure 1 and 2 show how the active links in a SG maintain strong Graph structure.

If at t= t1, ψ (u) k ,
If not go to step 9.

k {0,1, 2, 3, ..., n 1} , Go to step 11,

5 SECTION IV: PROPERTIES OF N A

Step 11: Search u , for ψ (u) = n .Select R=u.

Step 12 : Select next SG and perform steps 3 to 11. Step 13: Repeat step 12 till all SG gets active links.
Step 14: Connect pair of disjoint SGs using one NE and make it active.If there remains nodes which doesnot belong to any SG join those nodes by active NEs.
Step 15: Stop.

Theorem 5. 1: The active links of NA simulates a caterpillar.

Proof: The active links of NA are formed by connecting disjoint stars by disjoint NEs.There fore the removal of 1-degree vertices gives a path.Hence the proof.

Theorem 5. 2:

As r r → ∞ , NN tends to a star with centre the root node.

Proof: Let r → ∞ .Then all nodes exists in SG(r) .As per NA if

IJSER © 2012 http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 3, Issue 12, December-2012 4

ISSN 2229-5518

ψ (u) = n then n is selected as root node R and all other ver-

tices ui’s are connected by the edges uui. i.e, NN tends to a
Star with centre R.

Theorem 5.3:If all nodes of NE’s in an NN tends to root nodes then NN simulates the graph obtained by fusing each vertex of Pn with the apex vertices of K1,mi , i= 1,2,…,n+1.

Proof: Let e1, e2, e3,...., en be the edges NEs in NN.Let Pn be the path connecting ei’s.Its obvious that there exists n disjoint spheres SG(r) .Let K1,mi be the strong graph structure in the ith sphere.As NEs tends to root nodes,all nodes of Pn tends to Root nodes since Pn is formed by connecting ei’s.Therefroe NN simulates the graph obtained by fusing each vertex of Pn with the apex vertices of K1,mi , i= 1,2,…,n+1.

Theorem 5. 4: NN is strong and admits odd graceful labeling if all NSG has equal number of edges and NE’s form a cycle of root nodes and even order.

Proof: Let Cn be the cycle of even order formed by NE’s with root nodes v1, v2, v3,,… vn.Let K1,m be the active links in each NSG.Denote the pendant nodes of K1,m by vi,j where 0 < i < n+1 and 0 < j < m+1.Now |V(NN)|=|E(NN)|= n(m+1).This type of a Graph is Odd Graceful [8].

To prove that NN is strong.

Let ψ be the Odd Graceful labeling. Consider the link vi vi+1, i is

even and both ψ (vi ),ψ (vi +1 ) are non zeros.Then its clear that

there exixsts a strong edge for n > 7 and m > 2.. In this model of

NN ,The number of root nodes = n, the number of active links

l = n(m+1) and the number of active nodes = n(m+1).

6 SECTION V: PERFORMANCE ANALYSIS OF N A

Using AODV protocol and NS2 simulation tool, the ef- fectiveness of NA is measured.It is discovered that NA gives better parameters comparing with the existing method TAP.The result for a 500mx500m region, deploying 100 nodes is shown in the following tables.
7 CONCLUSIONS
The application of Stong Graphs in wireless networks is discovered. A virtual backbone structure is constructed us- ing Nishads algorithm.The properties of Nishad Graph and Nishads Algorithm is proved.The performance of Nishads Algorithm is measured and discovered that NA is more effec- tive than existing mehod TAP.The method to find the number of strong and weak edges of labeled graphs is under investiga- tion.
REFERENCES:
[1] Nishad T M,“Strong Graphs Its properties and some families of Strong Graphs”. Published in IJS- ER, ISSN 2229-5518, Volume3, Issue10, October 2012.
[2] S. Narayanaswamy, V. Kawadia, R. S. Sreenivas, and P. R. Kumar, “Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the COMPOW protocol,” in Proc. European Wire- less 2002 (EWC’02), February 2002, pp. 156–162.
[3] F. Akyildiz, J. McNair, J.S.M. Ho, H. Uzunalioglu, W. Wang, “Mobility management in next- generation wireless systems, Proceedings of the IEEE
87 (8) (1999) 1347–1384.August.
[4] M.Ibrahim Moussa.”An algorithm for odd graceful labeling of the union of paths and cycles”. Interna- tional journal on application of graph theory in wireless and hoc networks and sensor networks (Graph-Hoc) vol.2,No.1,March 2010.
[5] S.K.Vaidya,Lekha Bijukumar and Shanker- sinh.”Odd graceful labeling of some new graphs” vol.4,No.10, October 2010.Canadian center of Science & Education.
[6] Dr.A.Solairaju,C.Vimala and A.Sasikala “Edge-odd grace fullness of the graph s2Osn.” International journal of computer applications (00975-8887) Vol.9,No.12,November 2010.
[7] Dr.A.Solairaju, A.Sasikala and C.Vimala “Edge odd gracefulness of product of P2 and Cn. “Interna- tional journal of computer applications (00975-
8887), Vol.10, No.10 November 2010.
[8] S K Vaidya and B Lekha “New families of odd gra- cefull graphs”. Int.J.open Problems compt Math Vol.3,No.5 December 2010 ISSN (1998-6262).
[9] A.Solairaju,P.Muruganantham “Even vertex grace- ful of Path, Circuit, Star , Wheel, same extension friendship graphs and Helm graph.” IJCA (0975-
8887) Vol.10, No.6 November 2010.

IJSER © 2012 http://www.ijser.org