1. Introduction

The subject of edge – magic labelings of graphs had its origins three decades ago in the work of Kotzing and Rosa [9,10] on what they called magic valuations of graphs (which are also commonly known as edge-magic total labeling see[4]). Interest in these labelings has been lately rekindled by a paper on the subject due to Ringel and Llado [11]. Shortly after this, Enomoto, Llado, Nakamigawa and Ringel[3] defined a more restrictive form of edge-magic labelings namely super edge magic labelings which Wallis [12] refers to as strong edge – magic labelings.

By G(p, q), we denote a graph having p vertices and q edge, by V(G) and E(G), the vertex set and the edge-set of G respectively. But the vertices and edges are called the elements of the graph G. A graph (p, q) is said to have an edge magic with the magic constant k (which is independent on the choice of any edge uv of G) if there exists a one one– to –one mapping f:V(G) U E(G) à {1, 2,……,p+q} such that f(u) + f(v) +f(uv) =k for all uv ∈ E (G). If such a labeling exists, then magic constant k is called valence of f and G is said to be edge –magic graph. Given an edge magic f of a graph G (p, q), the Function f(x) such that = p+q+1-f(x) for all elements x ∈G is said to be complementary to f(x).

Two edge magic f₁ and f₂ of G are equivalent if f₁=f₂ orf₁=_. An edge magic f of G is said to be self complementary edge magic if f=

Figure 1.

The edge magic strength of a graph G is denoted by ems(G) and is defined as the minimum of all constants where the minimum is taken over all edge magic labelings of G. ems(G) = min {k: f is an edge magic labeling of G} similarly the concept of the complementary edge magic strength of a graph is introduced. The complementary edge magic strength of G is denoted by cems(G) and is defined as the minimum of all constants where the minimum is taken over all complementary edge magic labeling of G. cems (G) = min {: is an complementary edge magic labeling of G}.

In this paper, the complementary edge magic strength of some well known graphs such as K_{m, n} (m,n ≥ 1), C_n (n ≥ 3), np₂ (n ≥ 1), f_n, B_n and nG (n ≥ 2) where G is bipartite or tripartite are obtained. The reader is directed to Chartered and Lesniak[2] or Hartefield and Ringel[8] for all additional terminology not provided in this paper. The following theorem is every useful for the main results.

Theorem A [1] An complementary edge – magic graph G satisfies the following equation

where is complementary edge magic labeling of G and T=p+q.

Main Results

In this section we proceed to study the complementary edge magic strength of K_{m, n}, C_n, f_n=P_n+k₁ and B_n = K_{1, n} x K₂ and nG, where G is bipartite or tripartite.

Theorem1. A complete bipartite graph Km, n is complementary edge magic strength if m, n ≥ 1.

Proof: Let G be a complete bipartite graph K_{m, n} with vertex set V partitioned into two subject V₁ and V₂ where V₁={u₁, u₂,………u_m} and V₂={v₁,v₂,……v_n} and

let f: VUEà {1,2,…..,m+n+mn}

Then,

It is easy to see that f extends to a complementary edge magic labeling of K_{m, n} with the magic constant.

Complementary edge magic strength: Now by Theorem

A

Thus scems (K _{m, n}) = 2(mn+n+1)

The following theorem is the complementary edge magic strength of cycle C_n for every integer n ≥ 3.

Theorem2. The cycle C_n is complementary edge magic and complementary edge magic

strength is where n is an integer.

Proof: Let C be the cycle with

V (C_n) = {v _i: 1 ≤ i ≤ n} and E (C_n) = {v_i: v _i+1 : 1 ≤ i ≤ n²} where i is taken modulo n (replacing o by n)

We discuss the following cases.

Case I: n is odd say n=2m +1 where m is positive integer.

Consider the function f: V(G) U E (G) à {1,2,…,2n}

Defined as

Thus f is a complementary edge magic of cycle C_n with magic constant 3n+2

Complementary edge – magic string:

Case 2. n ≡ o (mod 4) say n = 4l where l is the positive integer, f is defined as

Next we prove that

f(v_i)+f(v_i+1)+f(v_iv_i+1) = for all i = 1,2,..,4l

Sub case 2.1 Let i ∈ {4, 6, 8.., 2n-4,2n} U {n+1,2n-1} Then

f (v_i)+f (v_i+1)+f (v_iv_i+1) = (2n+1-i)+(n-i-1)+(3+2i) =3(n+1)

Sub case 2.2 Let i = 2l-1 then

f (v_2l-1)+f (v_2l)+ f (v_2l-1v_2l)=(2n-2l+2)+(2n-2l)+1=3(n+1)

Sub case 2.3 Let i ∈ {2l, 2l+2,…, 4l-4} Then

f (v_i)+f (v_i+1)+f (v_iv_i+1) = (2n-i)+(n-i)+3+2i=3(n+1)

Sub case 2.4 Let i = 2l-2 Then

f (v_4l-2)+f (v_4l-1)+f (v_4l-2 v_4l-1)=(2n+2)+(2n-1)+2=3(n+1)

Sub case 2.5 Let I ∈ {2l+1, 2l+3,..,4l-3}, Then

f (v_i)+f(v_i+1)+f (v_iv_i+1) = (n+1-i)+(2n-1-i)+(3+2i)=3(n+1)

Sub case 2.6 Let i ∈ {2l+1, 2l+3,…4l-3} Then

f (v_i)+f (v_i+1) + f (v_iv_i+1)= (n-i)+(2n-i)+(3+2i)=3(n+1)

Sub case 2.7 Let i = 4l-1. Then

f (v_4l-1)+f (v_4l)+f (v_4l-1v_4l)=(2n-1)+(3)+(n+1)=3(n+1)

Sub case 2.8 Let i = 4l. Then

f (v_4l)+f(v₁)+f (v_4lv₁)= 3+(2n)+n=3(n+1)

Therefore is a complementary edge magic of the cycle C_n with the magic

Constant= 3 (n+1)

Complementary edge magic strength:

Case 3. n ≡ 2 (mod 4) that is n = 4l+2. Define the function

Next we prove that f (v_i)+f (v_i+1)+ f (v_iv_i+1) = for all i = 1,2,…..,4l+2

Subcase 3.1 Let i = 1 Then

Sub case 3.2 Let i = {3,5,..,2l-1} Then

Sub case 3.3 Let i = 2l+1. Then

Sub case 3.4 Let i = {2l+3, 2l+5,…, 4l-1} Then

Sub case 3.5 Let i = 4l+1. Then

Sub case 3.6 Let i = 2. Then

Sub case 3.7 Let i = 2k+2. Then

Sub case 3.8 Let i = 4l+2. Then

Sub case 3.9 Let i ∈ {4,6,…2k}. Then

Sub case 3.10 Let i ∈ {2l+4, 2l+6,….4l}. Then

Thus f is a complementary edge magic function of the cycle C_4l+2 with the magic constant =2(3n-5l-2)= (7n+2)/2

Complementary edge magic strength:

Theorem 3. Let G = nР₂ be a regular graph of degree one. Then G is a Complementary edge magic strength if and Only if n is odd.

Proof: Since (3n+1)/2 must be necessarily an integer. Hence it follows that n must be odd say n= 2l+1

Let u₁, u₂, …. u_n and v₁, v₂,….,v_n; u₁v₁, u₂v₂… u_nv_n be vertices and edges of G respectively. Define f by

And

Now we show that

Complementary edge magic strength:

Theorem 4. The fan f_n = P_n+K₁ is a complementary edge magic for any positive integer n

Proof . Let V (f_n) = {u} U { v_i :1≤ i ≤ n }

And E (f_n) = { uv_i : 1≤i≤n} U {v_iv_i+1 : 1≤i≤n-1}

Now define the function f: V (G) U E(G)"{1,2,…..,3n} as follows

Observe that f(x)+f(y)+f(xy)=6n for every edge xy ∈ E (fn)

Also notice that alternative type labeling is as follows:

And f (u) = 3n. Thus all integers 1,2,…,3n are used exactly once. Hence f is an complementary edge magic labeling of f_n with magic constant (valence) 6n.

Complementary edge magic strength :

Theorem 5. The book Bn=K1,n x K2 is complementary edge magic strength for any positive integer n

Proof. Let Bn be the book defined as follows:

V (Bn) = {uv}U{uivi :1≤ i ≤ n} and

E (Bn) = {uv}U{uui, vvi, uivi : 1 ≤ i≤n}

Now consider the function f : V(B_n)UE(B_n)" {1,2,..,5n+3}

Where

Finally observe that f is complementary edge magic labeling of B_n having valence 8n+6

Complementary edge magic strength:

This section has a tool that allows us to generate infinite classes of disconnected complementary edge magic n- partite graphs with relative case where n = 2,or 3. Previously no such a technique was available for graphs within those classes sec[6] except in[5].

Theorem 6. If G is a complementary edge magic bipartite or tripartite graph and n is odd then nG (n ≥ 2) is complementary edge magic.

Proof. Assume that n≥3. If (p,q) graph G is a complementary edge magic bipartite or tripartite graph with partite sets A, B, C [Let C=Φ if G is bipartite ] then let

E(G) = AB U AC U BC where the juxta-position of two partite sets denotes the set of edges between those two sets.

Let f :V (G)UE(G)"{1,2,…..,p+q} to be an arbitrary complementary edge magic labeling of G. Then X ≡ nG to be the graph with vertex set

V(X)= (A_iB_iUA_iC_iUB_iC_i) where x_i ∈ Y_i for 1 ≤ i ≤ n if and only if x ∈ Y (Y is one of the sets A,B,C,AB,AC,BC)

Consider the labeling g : V(X)UE(X)"{1,2,…..n (p+q)} such that

Clearly g is a complementary edge magic labeling of X with valence

g(u)+g(v)+g(uv)=2n(p+q)-3(n-1)/2 for each edge uv ∈ E(X) where kf is the valence of f.

Next to observe that g(V(H)UE(H))={1,2,…,n(p+q) is spread by the function g to the entirety of its range.

In the above theorem n can not be even for Kotzig and Rosa[9] have shown that the forest nP₂ is edge magic if and only n is odd

Immediately the corollary follows from above Theorem

Corollary: If n is odd and m>1 then 2-regular graph nC_2m is complementary edge magic.

Poof. Kotzig and Rosa have shown that all cycles are edge magic. But an alternative labeling of even cycles can be found in[7].