PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

Send a file File manager PDF Toolbox Search Help Contact



54I18 IJAET0118732 v6 iss6 2791 2794 .pdf



Original filename: 54I18-IJAET0118732_v6_iss6_2791-2794.pdf
Author: Editor IJAET

This PDF 1.5 document has been generated by Microsoft® Word 2013, and has been sent on pdf-archive.com on 04/07/2014 at 08:03, from IP address 117.211.x.x. The current document download page has been viewed 458 times.
File size: 414 KB (4 pages).
Privacy: public file




Download original PDF file









Document preview


International Journal of Advances in Engineering & Technology, Jan. 2014.
©IJAET
ISSN: 22311963

NEW CONSTRUCTION ON COMPLEMENTARY SUPER EDGE
MAGICNESS OF GRAPHS
Neelam Kumari1 and Seema Mehra2
Department of Mathematics, M.D. University, Rohtak (Haryana), India

ABSTRACT
An edge magic total labeling of a graph with p vertices and q edges is a bijection from the set of vertices and
edges to 1,2,……………,p+q such that for every edge the sum of the label of edge and the label of its two end
vertices are constant. This type of labeling is called super edge magic labeling if smallest labels are assigned to
vertices. In this paper, a new graph characteristic, the complementary super edge magic labeling is introduced
and we investigate whether several family of graphs have complementary super edge-magic labeling or not?

KEYWORDS: Graph Labeling, Magic Labeling,

Edge -Magic Labeling, Complementary Edge Magic

Labeling.

I.

INTRODUCTION

Graph labeling is one of the fascinating areas of graph theory with wide range of applications.
Graph labeling were first introduced in the 1960’s where the vertices and edges are assigned real
values or subset of a set subject to certain conditions i.e. the most common choice of domain are
the set of vertices (vertex labeling),the edge set alone (edge labeling), or the set of all vertices and
edges (total labeling ).The concept of magic labeling (magic graph) was introduced by Kotzig
and Rosa. They defined a magic labeling of a graph G( V,E) as a bijection f :V U E→ {
1,2,……..,p+q } such that for all uv є E(G), f(u)+f(v)+f(uv) are the same. An edge-magic total
labeling of a graph G with p vertices and q edges is a bijection from the set of vertices and edges
to 1,2……….p+q , such that for every edge the sum of the label of the edge and the sum of its
two end vertices are constant i.e. f(u) + f(v) + f(uv) = k for every edge uv of G , k is called magic
constant . If such a labeling exists, then the magic constant k is called valence of G and G is said
to be edge- magic graph. An edge-magic labeling f is called super edge-magic if f(V(g)) =
{1,2,…………p} and f(E(G))={p+1,p+2,……….p+q}.Given an super edge –magic labeling f of a
graph G(p, q), the function f̅ (x) such that f̅ (x)=p+q+1-f(x) for all x є G is said to be
complementary super edge –magic labeling to f(x).
Figure 1.[a, b] represents an example of Super edge-magic labeling and Complementary super
edge – magic labeling

2791

Vol. 6, Issue 6, pp. 2791-2794

International Journal of Advances in Engineering & Technology, Jan. 2014.
©IJAET
ISSN: 22311963

Figure 1[a]. Super Edge Magic Labeling

Figure1[b]. Complementary Super Edge Magic Labeling

Two super edge magic f 1 and f 2 of G are equivalent if f 1 =f 2 or f 1=f2̅ . An super edge magic f of G is
said to be self complimentary super edge magic if f=f̅
We denote by sems (G) the super edge magic strength of a graph G and are defined as the minimum
of all constants where the minimum is taken over all edge-magic labeling of G. Similarly the concept
of Complimentary super edge magic strength of a graph G is introduced. The complimentary super
edge magic strength of graph G is denoted by csems (G) and is defined as the minimum of all
constants k1 , where the minimum is taken over all complementary super edge-magic labeling of G.
Csems(G) = min{ k1 : f̅ is an complimentary super edge-magic labelingofG}.
In edge – magic labeling ems (G) =cems (G), but in super edge magic labeling it is not necessary that
sems (G) =csems (G). In this paper, we investigate whether several families of graphs are
complementary super edge-magic or not? The following theorem and lemma are very useful for the
main results.
Theorem [A] An complementary edge –magic graph G satisfies the following equation
qk1 = T (T+1)/2 +∑ [dvi-1] f (vi)
Where T = p+q, i.e. the sum of number of vertices and edges in graph G.
Lemma [B] A (p, q) graph G is super edge -magic if and only if there exist a bijective function
f: V (G) → {1, 2,…………….p} such that the set
S = {f (u) +f (v): uv єE (G)}
Consists of q consecutive integers. In such a case, f extends to a super edge – magic labeling of G
with valence k= p+q+s, where s = min (S) and
S = {k-(p+1), k-(p+2)…k – (p+q)}.

II.

MAIN RESULTS

Theorem.2.1: The cycle Cn has complementary super edge – magic labeling if and only if n is odd
5𝑛+3
7𝑛+3
and sems = 2 , csems = 2 .
5𝑛+3

Proof. Since 2 must be necessarily an integer. Hence it follows that n must be odd.
Now let n = 2m+1 be an odd integer, where m is any integer.
V (Cn) = {v0, v1 , ……………….v n-1 },
E (Cn) = {v n-1v0 } U {vi vi+1 |0 ≤ i ≤ n-2}.
Define
𝑖+2
2

f (vi) = {

m+

if i is even,
𝑖+3
2

if i is odd.

f (v n-1v0) = 2n,
f (vi vi+1) = 2n – 1 –i
for 0 ≤ i ≤ n-2 .
5𝑛+3
Then f is a super edge – magic labeling with the magic number
.It is easy to see that f extends to
2

a complementary super edge-magic labeling of Cn ( n is odd) with the magic constant k1 =
complementary super edge – magic function is defined by

2792

7𝑛+3
.
2

The

Vol. 6, Issue 6, pp. 2791-2794

International Journal of Advances in Engineering & Technology, Jan. 2014.
©IJAET
ISSN: 22311963
f̅ ( vi )= = {

4𝑛−𝑖
2
4𝑛−2𝑚−𝑖−1
2

if i is even,
if i is odd.

f̅ ( vn-1 v o )= 1,
f̅ ( vi vi+1 )=2+i.
7𝑛+3
Thus csems ( Cn )= 2 .
Example 1. To support the theorem 2.1 we give an example of C5 having complementary super edge7𝑛+3
magic 2 .
Solution:

Super edge magic labeling for
C5 with sems=14

Complementary super edge magic
labeling for C5 with Csems =19

Theorem 2.2: The ladder graphs Ln=
̃ Pn×P2 is complementary super edge-magic, where n is odd and
11𝑛+1
19𝑛−7
super edge magic strength is 2 and complementary super edge magic strength is 2 .
Proof: Let Ln be ladder with
V (Ln) = {ui ,vi ; 1 ≤ i ≤ n}
and
E( Ln) ={ uiui+1, vi vi+1, uj vj : 1 ≤ i ≤ n-1 ,1 ≤ j ≤ n }
Now consider the following function
f : V( Ln ) ={ 1,2…….2n },
where

f(x) =

𝑖+1
2
𝑛+𝑗+1
2
3𝑛+𝑖
2
2𝑛+𝑗
2

𝑖𝑓 x = ui , i odd and 1 ≤ i ≤ n ,
𝑖𝑓 x = uj , j even and 1 ≤ j ≤ n ,
𝑖𝑓 x = vi , i odd and 1 ≤ i ≤ n ,

𝑖𝑓 x = vj , j even and 1 ≤ j ≤ n .
{
Then by using Lemma [B] we conclude that f extends to a super edge-magic labeling of Ln with
11𝑛+1
valence
. But to find out complementary super edge-magic labeling of Ln (first we find out
2
E(Ln) and ) or we need E(Ln) which are given by
f: E (Ln) → { 2n+1 ,2n+2,……………………………3n-2}

f(xy)=

10𝑛−𝑖−𝑗−1
2
6𝑛−𝑖−𝑗+1`
2

if x = ui y = uj , where i is odd and 𝑗 𝑖𝑠 𝑒𝑣𝑒𝑛,
if x = vi y = vj , where i is odd 𝑎𝑛𝑑 𝑗 𝑖𝑠 𝑒𝑣𝑒𝑛,

4n − i
if x = ui , y = vi 1 ≤ i ≤ n.
{
The complementary super edge-magic function is defined by

2793

Vol. 6, Issue 6, pp. 2791-2794

International Journal of Advances in Engineering & Technology, Jan. 2014.
©IJAET
ISSN: 22311963
f̅ : V (G) U E (G) → {1, 2……………2n………….5n-2}
where
10𝑛−𝑖−3
if x = ui i odd and 1 ≤ i ≤ n,
2
f̅ (V

̅
f(xy)=

𝑖+𝑗−1
x=
2
4𝑛+𝑖+𝑗−3
2

9𝑛−3−𝑖
2
(G))= 7𝑛−2−𝑖
2
8𝑛−2−𝑖
{ 2

if x = uj j even and 1 ≤ j ≤ n,
if x = vi , i odd and 1 ≤ i ≤ n,
if x = vj , j even and 1 ≤ j ≤ n.

ui, y = uj where i is odd and j is even, 1 ≤ j ≤ n,
x = vi, y = vj , where i odd 𝑗 𝑒𝑣𝑒𝑛,

{n + i − 1 if x = ui y = vj for 1 ≤ i ≤ n.
19𝑛−7
Hence the complementary super edge-magic strength is given by 2 , where n is an odd integer.
With this paper, we hope that interest in super edge-magic and complementary super edge-magic
labeling will aroused among those who study graph labeling.

REFERENCES
[1].
[2].
[3].
[4].
[5].
[6].
[7].
[8].
[9].
[10]
[11]

A. Kotzig and A. Rosa, Magic valuation of finite graphs, Canad math. Bull 13(1970) 451-461.
A. Kotzig and A. Rosa, Magic valuations of complete graphs, Publications du Centre de Recherches
Mathematiques Universite de Montreal, 175(1972).
A. Rosa. On certain valuation of the vertices of a graph. Theory of graphs, Internat. Symposium, Rome,
July 1966. Gordon and Breach. N.Y and Dunod Paris (1967), 349-355.
D.Craft and E.H Tesar on a question by Erdos about edge magic graph.Discrete Math.207 (1999)271276.
H. Enomoto, A Llado, T. Nakamigawa and G. Ringel, Super edge magic graphs SUT J. Math.
34(1998).
J.A.Gallian, Graph Labeling, Electron. J.Combin. 5(1998)(dynamic survey DS6)
R.M Figueroa-Centeno, R. Ichishima and F. A Muntaner Batle, Enlarging the classes of edge magic 2
regular graphs, (pre-print).
R.M. Figueroa-Centeno, R.Ichishima, The place of super edge-magic labeling among other classes of
labeling, Discrete Mathematics 231 (2001)153-168.
S. Roy and D.G. Akka, On Complementary edge magic of certain graphs, American Journal of
Mathematics and Statistics 2012, 2(3): 22-66.
S.W.Golomb, How to number a graph. Graph Theory and Computing, R.C.Read ed. Academic Press,
New York (1998), 23-37.
W. D Wallis, Magic Graphs, Birkhauser Boston (2001).

AUTHORS
Kumari Neelam obtained her M.Sc. and M.Phil. Degrees in Pure Mathematics from
Maharishi Dayanand University, Rohtak ( Haryana) INDIA. Presently Neelam is pursuing
her Ph.D. in M.D.U, Rohtak. Her research areas include Graph Labeling Magic Labeling,
Anti-Magic Labeling and Super Edge (Vertex) Magic Labeling.

Mehra Seema is working as Assistant Professor in Maharishi Dayanand University Rohtak (Haryana) INDIA.
Her research areas include Graph Labeling Magic Labeling, Anti-Magic Labeling and Super Edge (Vertex)
Magic Labeling.

2794

Vol. 6, Issue 6, pp. 2791-2794


54I18-IJAET0118732_v6_iss6_2791-2794.pdf - page 1/4
54I18-IJAET0118732_v6_iss6_2791-2794.pdf - page 2/4
54I18-IJAET0118732_v6_iss6_2791-2794.pdf - page 3/4
54I18-IJAET0118732_v6_iss6_2791-2794.pdf - page 4/4

Related documents


PDF Document 54i18 ijaet0118732 v6 iss6 2791 2794
PDF Document ijetr2150
PDF Document datastructureunit6
PDF Document graphtheoryandcombinatoricsunit3
PDF Document graphtheoryandcombinatoricssyllabus
PDF Document graphtheoryandcombinatoricsunit4


Related keywords