 Open Access
 Total Downloads : 330
 Authors : P. Shalini, D. Paul Dhayabaran
 Paper ID : IJERTV3IS20532
 Volume & Issue : Volume 03, Issue 02 (February 2014)
 Published (First Online): 20022014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Proper Colourings in Magic and Antimagic Graphs
P. Shalini
Cauvery College for Women, Tiruchirappalli, India.
D. Paul Dhayabaran
Bishop Heber College (Autonomous), Tiruchirappalli, India.
Abstract – In this paper, the new concept of proper colourings in vertex magic and antimagic graphs has been introduced. A bijection mapping that assigns natural number to verties or edges of a graph is called a labeling and graph labeling that have weights associated with each edge and or vertex has been taken for consideration. If all the vertex weights have the same value then the labeling is called magic. If the weight is different for every vertex then we call the labeling as antimagic. In this paper,mainly new inequalities on chromatic number related with magic and antimagic graphs are being established.
Keywords : vertex magic labeling, regular graphs, proper colourings,antimagic graphs.
1. INTRODUCTION
Definition 1.2
The chromatic number of a graph G is the minimum number of colours that is required to colour G. It is denoted by (G).
Definition 1.3
If every vertex in a graph G has the same degree r, that is = = r, then G is called a regular graph of degree r, or an rregular graph.
Theorem 1.1
If G is a vertex magic rregular graphs then the chromatic number satisfies the double inequality
In this paper, we consider only finite, simple and
undirected graphs. The graph G has vertex set V
= V(G) and edge set E = E(G) and we take = E and v =
V. Magic labeling was introduced by Sedlacek in 1963[5]. The notion of an antimagic graph was introduced by Hartsfield and Ringel in 1989[3]. Vertex magic graphs are graphs labeled with numbers in which every vertex and its
K – 1
v +
Proof Case: i
(G)
1 nr
2
incident edges adds upto the same number. This number is called magic number, vertex magic labeling are coloured with proper colourings. Let r be the degree of the vertex of a regular graph.
Main Results

Colourings in rregular magic graphs for r 2
The following are some of the basic definitions which are to be referred and has established some results.
Definition 1.1
Let Cn be a cycle graph. Let n be an odd integer.
Let V(G) be the set of all vertices in the cycle graph and E(G) be the set of an edges in the cycle graph.
The cycle graph consists of n vertices and n edges. Define f : V E {1, 2, 3, . . . , 2n} as follows :
For every vertex vi, the vertex magic labeling is defined for 1 i n respectively as follows:
f(vi) = (2n + 1) i for 1 i n
For every edge ei, the magic labeling is defined as follows for 1 i n
i 1 if i is odd
f(e ) = 2
A Bijection f : V(G) E(G) {1, 2, 3, . . . , v+} is called a vertex magic labeling if there is a constant K, such that vertex weight of every vertex in G is equal to the constant
i n 1 i
2
if i is even
K = f(x) +
y N(x)
f(xy)
9(R)
1 4
4(R)
3
5(B)
10(G) 8(B) 8 7
3 2
1(B)
6
Magic Number, K = 15
2(R)
6(B) 5
7(R)
Let C
be a cycle graph with vertex magic labeling, then
Magic number, K = 14
Let Cn be a graph with vertex magic labeling, then the vertices v1, v2, v3, v4, v5 are coloured with different colours
by proper colouring and the number of colours used for
n
the vertices v1, v2, v3, v4 are coloured with different colours by proper colouring. The colours used for colouring this graph is 2.
Therefore (G) = 2
colouring this graph is 3. Therefore, (G) = 3
K – 1
v +
(G)
. . . (3)
Therefore, K – 1
v +
(G)
. . . (1)
The general condition of rregular graph is denoted as 1 nr
2
The general condition of rregular graph is denoted as 1 nr
2
Therefore, (G)
1 nr
2
. . . (4)
Therefore, (G)
1 nr
2
. . . (2)
from equation (3) & (4)
It is easily verified that K – 1
(G) 1 nr.
from equation (1) & (2)
v + 2
It is easily verified that K – 1
v +
(G) 1 nr.
2
Thus, an even cycle satisfies the condition for colourings in vertex magic labeling for 2regular graphs.
Thus, an odd cycle satisfies the condition for colourings in vertex magic labeling for 2regular graphs.
Case: ii
Let Cn be an even cycle Let n be an even integer
Let V(Cn) be the set of all vertices and E(Cn) be the set of all edges in G.
Let V(Cn) = {v1, v2, v3, . . . , vn}
Let E(Cn) = {vnv1} {vivi+1/1 i n1}
Define f : V E {1, 2, 3, . . . , 2n} as follows :
For every vertex vi, the vertex magic labeling is defined as follows.
Case: iii
Let the graph G be generalized Petersen graph Let n be an even integer.
Let V(Cn) = {v1, v2, v3, . . . , vn}
Let E(Cn) = {e1, e2, e3, . . . , en}
Define f : V E {1, 2, 3, . . . , 2n + 6} as follows :
For every vertex vi is defined respectively as follows :
2n + i ; i = 1
f(vi) =
2n + 8 – i ; 2 i 6
2n – i – 3 ; 7 i 8
i + 3 if 1 i 2
2n – i + 3 ; 9 i 12
f(v ) = i + 1 if i = 3
For every edge e , is defined respectively as follows :
i i
2 i for 1 i
12
i – 3 if i = 4
For every edge ei, the edge labelings is defined as follows :
f(ei) =
3n i 1 for 13 i
18
i + 2 if i 1
f(ei) = 2n i + 1 if 2 i 3
2i if i = 4
25(R)
1
6 24
14(G)
5(B)
1(R)
14
13
10 7
2(B)
26(B)
15(R) (B)
30(G) 6
19 12 13 23
11 7
5 2
9
12 8 15
27(G)
16
20 B
4
10 8
9
17 G 21
18
R 22
3
29(B)
4(G)
11
Magic number, K = 45
3(R)
28(R)
Magic number, K = 56
The generalized Petersen Graph is labeled with vertex magic, then the vertices are coloured with different colours by proper colouring and the number of colours used for
The complete graphs is labeled with vertex magic, then
the vertices in the complete graph is coloured with different colours by proper colouring and the number of colours used for colouring the complete graph is 5.
Therefore, (G) = 5
colouring this graph is 3.
Therefore, K – 1
v +
(G)
. . . (7)
Therefore, (G) = 3
The general condition of rregular graph is denoted as 1 nr.
Therefore, K – 1
v +
(G)
. . . (5)
Therefore, (G)
1 nr
2
2
. . . (8)
The general condition of rregular graph is denoted as 1 nr.
2
from equation (7) & (8) It is easily verified that
Therefore, (G)
1 nr
2
. . . (6)
K – 1
v +
(G) 1 nr.
2
from equation (5) & (6)
K – 1
v +
(G) 1 nr.
2
Therefore, the complete graph satisfies the condition for colourings in vertex magic labelings for 4regular graphs
Thus, a generalized Petersen Graph satisfies the condition for colourings in vertex magic labeling for 3 regular graphs.
Case: iv
Let G be a complete graph

COLOURINGS IN ATIMAGIC GRAPHS
The following are some of the basic definitions which are to be referred and has established some results.
Definition 2.1
The weight of a vertex x V, under the labeling , is
Let n be an odd integer.
Let V = {v1, v2, v3, . . . , vn} be the vertices.
wt(x) = (x) +
(xy) , where for every x V, (x) = 0
yN(x)
Let E = {e1, e2, e3, . . . , en} be the edges.
Define f : V E {1, 2, 3, . . . , 3n} as follows : f(vi) = i for 1 i n
f(ei) = n + i for 1 i2n
under an edge labeling and (x) 0 under a total labeling.
Theorem 2.1
If G is a vertex antimagic graphs then the chromatic number satisfies double inequality.
7 (G)
1 (R)
11
8
2 (B)
Proof :
t1 1
t0
(G)
a – d + d n
14
6 (B)
12
3 (R)
Case i
Let Pn be the path and n be an odd integer.
10
5 (R)
9
4 (B)
13
Let {v1, v2, . . . , vn} be the vertices and {e1, e2, . . . , en} be the edges of the path Pn receive the following labels.
f(v1) = 1
f(vn) = n
f(vi) = n i + 1 for 2in1 and the edge receive the labels
i i+1 2n 1 i for i is even
f(v v ) = 2n 1 i for i is odd
Let Cn be the cycle and with vertex antimagic labeling, then the vertices v1, v2, v3, v4, v5, v6, v7 are coloured with different colours by proper colourings and the number of colours used for colouring this graph is 3.
Therefore, (G) = 3
Let t1 = max{20,22,24,26,28,30,32}
t1 = 32
Let t0 = min{20,22,24,26,28,30,32}
t0 = 20
R B
1 12 6 13
R
5 10
B R B R
4 11 3 8 2 9 7
t1 1
t0
G
. . . (3)
Let Pn
be the path and with vertex antimagic labeling,
G
a – d + d
n
. . . (4)
then the vertices v1, v2, v3, v4, v5, v6, v7 are coloured with different colours by proper colourings and the number of
colours used for colouring this graph is 2.
From (3) and (4)
It is easily verified that
Therefore, (G) = 2
Let t1 = max{13, 16, 19, 22, 25, 28, 31}
t1 1
t0
G
a – d + d n
t1 = 31
Let t0 = min{13, 16, 19, 22, 25, 28, 31}
Then the vertex weights form an arithmetic progression with
5n + 5 5n + 9
t0 = 13
difference two, namely
, , . . .
2 2
t1 1
t0
G
. . . (1)
Conclusion
In this Paper,a new double inequalities has been
a – d
n
+ d
G
established. Further,it has been verified for magic and antimagic graphs. Finally,we conclude that new inequalities
G
a – d + d n
. . . (2)
on chromatic number related with magic and antimagic graphs are satisfied.
From (1) and (2)
It is easily verified that
REFERENCES
t1 – 1
G
a – d + d

G.S.Bloom, S.W.Colomb, Applications of the numbered
t0 n
Then the vertex weights form an arithmetic progression with difference two, namely 2n – 1, 2n + 2, 2n + 3, 2n + 5, . . .
Case ii
Let Cn be the cycle and n be the number of vertices.
Label the vertices and the edges of Cn by f(vi) = n i + 1 for 1 i n
undirected graphs, Proc. IEEE, 65(1977), pp.562570.

A.Gallian, A Dynamic Survey of Graph Labeling, Electronic Journal of Combinatorics, 17(2010) # DS6.

N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, BostonSan DiegoNew York London,1990.

J.A. MacDougall, Mikra Millar, Slamin and W.D.Wallis, Utilitas Math in Press.

J. Sedlacek, Problem 27, Theory of Graphs and Its Applications, proc. Symposium Smolenice ,June(1963), pp.163167.
n i 1
for i is odd
f(v v
)= 2
i i+1
2n 2 i
2
for i is even