Proper Colourings in Magic and Antimagic Graphs

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 anti-magic 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 anti-magic graphs are being established.

Keywords : vertex magic labeling, regular graphs, proper colourings,anti-magic 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 r-regular graph.

Theorem 1.1

If G is a vertex magic r-regular 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

1. Colourings in r-regular 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 r-regular graph is denoted as 1 nr

   2

   The general condition of r-regular 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 2-regular graphs.

   Thus, an odd cycle satisfies the condition for colourings in vertex magic labeling for 2-regular 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 n-1}

   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 r-regular graph is denoted as 1 nr.

   Therefore, K – 1

   v +

   (G)

   . . . (5)

   Therefore, (G)

   1 nr

   2

   2

   . . . (8)

   The general condition of r-regular 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 4-regular 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

2. COLOURINGS IN ATI-MAGIC 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 anti-magic 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 2in-1 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 anti-magic graphs are satisfied.

From (1) and (2)

It is easily verified that

REFERENCES

t1 – 1

G

a – d + d

1. 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.562-570.

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

3. N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Boston-San Diego-New York- London,1990.

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

5. J. Sedlacek, Problem 27, Theory of Graphs and Its Applications, proc. Symposium Smolenice ,June(1963), pp.163-167.

n i 1

for i is odd

f(v v

)= 2

i i+1

2n 2 i

2

for i is even