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.

2. Objective

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₂ or f₁=_. 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}.

3. Methods

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.

4. Results

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,

f (v_i) = m+n+mn+1-i f(v_j) = mxn+n+1 – (m+1)j

f(a_ib_j) = -m+(m+1)j +i

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

= f(v_i) + f (v_j) + f(a_ib_j)

= [m+n+mn+1-i] + [mn+n+1 – (m+1)j] + [-m+(m+1)j +i]

= 2mn+2n+2

= 2(mn+n+1)

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

and,

Since we have f (V_i) = {2,4,6,10,….2n}

f (v _i v _i+1) = {1,3,5.(2n-1)}

f (v_n) + f (v₁) + f (v_nv₁) = 2n+(n+1)+1 = 3n+2

f (v _i)+ f (v _i+1) + f (v _i v _i+1) = (2n+1- i ) + (n-i) + (1+2i) =3n+2 for i=1,2, n-1

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

Clearly f(v_i) = { 4,6,8,…..2n-4,2n} U {n+1, 2n-1}

f(v_iv_i+1) = { 1,3,5,…..n-1, n+3,n+5,…,2n-3} U {2, 2n-2}

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

Since {f v_i } = { 4l + 2, 4l+3,….., 6l+1, 6l+2,6l+4,6l+5,……8l+4}

{f (v_i v_i+1)} = { 1,2,…,4l, 4l+1, 6l+3}

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

f (v_i)+f (v_i+1)+ f (v_iv_i+1)= 2n+(2n-6l-2)+(2n-4l-2)

=2 (3n-5l-2)=(7n+2)/2

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

f (v_i)+f (v_i+1)+f (v_iv_i+1)= (2n+1/2 – i/2)

+ {2n-2l-1- (i+1)/2}+(2n-8l-3-i)

= 2 (3n-5l-2)= (7n+2)/2

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

f (v_2l+1)+ f (v_2l+2)+f (v_2l+1v_2l+2)

= (2n-1)(2n-l-1)+(2n-8l-3)=3(2n-5l-2)=(7n+2)/2

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

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

+{2n-2l-1-(i-1)/2)+(2n-8l-3+i)

= 6n-10l-4 =2 (3n-5l-2) = (7n+2)/2

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

f (v_4l+1)+f (v_4l+2)+f (v_4l+1,v_4l+2)= (2n-1/2- (4l+1)/2)

+(2n-2l-2)+(2n-6l-1)= 6n-10l-4 =2 (3n-5l-2)

= (7n+2)/2

Sub case 3.6 Let i = 2. Then

f (v₂)+f (v₂)+f (v₂v₃)= (2n-6l-2)+(2n-1)+(2n-4l+1)

= 6n-10l-4 = 2 (3n-5l-2) =(7n+2)/2

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

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

+(2n-l-1)+(2n-8l-1)=2(3n-5l-2)= (7n+2)/2

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

f (v_4l+2)+f (v₁)+f (v_4l+2v₁)= (2n-2l-2)+(2n+1)+(2n-6l-2)

=2(3n-5l-2) =(7n+2)/2

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

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

+(2n-i/2)+(2n-8l-3+i)= 2(3n-5l-2)= (7n+2)/2

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

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

+(2n-1-i/2)+(2n-8l-3+i)=2 (3n-5l-2)=(7n+2)/2

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:

= {2n(2n+1)}/2 + ∑f (v_i)

= {2n(2n+1)}/2+[ (n+2)/2+ (n-1)/2 x{2 (n+2)+1 (n-1)}]

== 7n²+ 2n/2

= 7n+2/2.

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

We have {f u_i } = {2n+1, 2n+2, …..3n} and

{f (u_iv_i)} = {n+1,n+2,….., 2n}

Now we show that

= f (u_i)+f (v_i)+f (u_ivi)= (3n+1-i) + (3n-3l-i)

+(3n-6l-4+2i)= 9n-9l-3 = 3{(9n+1)}/2

Complementary edge magic strength:

= {3n (3n+1)}/2 Therefore, = {3(3n+1)}/2

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:

{f (v_2i+1) : o ≤ i ≤ |_(n-1)/2_|

= {3(n-i)+1 : 1 ≤ i ≤ |_(n+1)/2_|}

{f (uv_2i) : 1≤ i ≤ ┌ _(n-1)/2 ┐

= {3(n-i)+1 :1+|_(n+1)/2_| ≤ i ≤ n}

{f (v_i v_i+1): 1≤i ≤ n-1

= {3(n-i)+1 : 1+|_(n+1)/2_| ≤ i ≤ n}

{f (v_2i): 1≤ i ≤ ┌ _(n-1)/2 ┐

= {3(n-i)-1: o ≤ i ≤ |_(n-2)/2_|}

{f (uv_2i+1): 0 ≤ i ≤ |_(n-1)/2] _|

= {3(n-i)-1: 1+|_(n-2)/2_| ≤ i ≤ n-1}

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 :

= {3n(3n+1)}/ 2 +2∑{12n+3+5(-1)ⁱ-6i }/ 4

+ 3n(n-1)-(3n-2)- {6n+3+5(-1)ⁿ }/ 4

=1/2[9n²+3n+12n²+3n+∑5(-1)ⁱ-6n(n+1)/2

+6n²-15n+5/2-5/2(-1)ⁿ]

(2n-1) =1/2[24n²-12n+∑5(-1)ⁱ+5/2-5/2(-1)ⁿ]

=1/2[24n²-12n]/2n-1 = 6n if n is odd or even

Theorem 5. The book B_n=K₁,n^x K₂ is complementary edge magic strength for any positive integer n

Proof. Let B_n be the book defined as follows:

V (B_n) = {uv}U{u_iv_i :1≤ i ≤ n} and

E (B_n) = {uv}U{uu_i, vv_i, u_iv_i : 1 ≤ i≤n}

Now consider the function f :

V(B_n)UE(B_n)" {1,2,..,5n+3}

Where

5. Conclusions

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

Complementary edge magic strength

= (5n+3)(5n+4)/2+n(5n+3)

+n(1)+∑(3n+2-i)+∑(3n+2+2i)

= (25n²+35n+12)/2+5n²+4n+∑(6n+4+i)

(3n+1) = (35n²+43n+12) / 2 + n(6n+4)+ {n(n+1)}/2

{48n2+52n+12}/{2(3n+1)} = 8n+6

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 k_f 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].