AMERICAN JOURNAL OF MATHEMATICAL SCIENCE AND APPLICATIONS
2(1) • January-June 2014 • ISSN : 2321-497X • pp. 59-72
Z4 MAGIC LABELING OF SIMPLE GRAPHS
K. Jeya Daisy1 and P. Selvagopal2
1
Department of Mathematics, Holy Cross College, Nagercoil, India
2
Cape Institute of Technology, Levengipuram, Tirunelveli, India
ABSTRACT: For any non-trivial abelian group A under addition a graph G is said to be “A-magic” if there exists a
labeling f of the edges of G with non-zero elements of A such that, the vertex labeling f+ defined as f+(v) = �f(uv)
taken over all edges uv incident at v is a constant[4]. A graph is said to be “A-magic” if it admits an A-magic
labeling. In this paper we prove that Friendship graph, generalised prism graph, Goldner Harary graph, Herschel
graph, Grotzsch graph, Fish graph, Butterfly graph, Octahedral graph and Moser Spindle graph are Z4 magic. Also
we generalize that they are all Z4p magic graphs for any positive integer p.
Keywords: A-magic labeling, Z4 magic labeling, Z4p magic labeling.
AMS Subject Classification: 05C78
1. INTRODUCTION
By a graph, we mean a finite, undirected, simple graph without loop and multiple edges and for graph
theoretical terms we refer Harary [3] and for terms related to labeling we refer to J.A.Galian [2].
Definition 1.1
For any non-trivial abelian group A under addition a graph G is said to be “A-magic” if there exists a
labeling f of the edges of G with non zero elements of A such that the vertex labeling f+ defined as f+(v)
=�f(uv) taken over all edges uv incident at v is a constant.
We choose Z4 which is additive modulo 4 as the abelian group.
Definition 1.2
Friendship graph Fn can be constructed by joining n copies of the cycle graph C3 with a common vertex.
Definition 1.3
The graph CnXPm is called generalised prism.
Definition 1.4
The Goldner Harary graph is a simple undirected graph with 11 vertices and 27 edges.
60
American Journal of Mathematical Science and Applications 2(1), 2014
Definition 1.5
The Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges.
Definition 1.6
The Grotzsch graph is a triangle free graph with 11 vertices and 20 edges.
Definition 1.7
Fish graph is a graph on 6 vertices and 7 edges.
Definition 1.8
Butterfly graph is a planar undirected graph with 5 vertices and 6 edges.
Z4 Magic Labeling of Simple Graphs
61
Definition 1.9
The Octahedral graph is the 6 vertex 12 edge platonic graph having the connectivity of the octahedron.
Definition 1.10
The Moser Spindle graph is an undirected graph with 7 vertices and 11 edges.
2. MAIN RESULTS
Theorem 2.1
The friendship graph Fn is Z4 magic for all n.
Proof: Let V be the vertex set and E be the edge set of the friendship graph Fn. Then
V (Fn) = {u, v1(j), v2(j) /1� j �n}
E(Fn) = {uv1(j), uv2(j), v1(j) v2(j) / 1� j �n}
Define f : E (Fn) � Z4 – {o} by
( j)
f � uv1 � � 2 ; j =1 to n
( j)
f � uv 2 � = 2; j =1 to n
( j) ( j)
f � v1 v 2 � = 2; j =1 to n
Define f+: V(Fn) � Z4 by
f+(u) = f(uv1(j)) + f(uv2(j)); j =1 to n
f+(v1(j)) = f(uv1(j)) + f(v1(j) v2(j)); j =1 to n
f+(v2(j)) = f(uv2(j)) + f(v1(j) v2(j)); j = 1 to n
62
American Journal of Mathematical Science and Applications 2(1), 2014
Then we get
f+(u) = 0
f+(v1(j)) = 0; j = 1 to n
f+(v2(j)) = 0; j = 1 to n
Hence, f+ is constant and equals to 0 for all vertices of Fn.
f+ admits Z4 – magic labeling and hence Friendship graph is Z4 magic for all n.
Example 2.2: Z4 magic labeling of Friendship graph F4 is given below.
Figure 2.1: Z4 Magic Labeling of F4
Theorem 2.3
The generalised prism is Z4 magic.
Proof: Let G be a generalised prism
Let V(G) = { vij / i = 1 to n, j = 1 to m}
E(G) = { vij vij�1 / i = 1 to n-1, j = 1 to m} U { v nj v1j / j = 1 to m} U { vij vij / i = 1 to n, j = 1 to m-1}
Define f: E (G) � Z4 – {0} as
f � v1i v1i �1 � � 1 (i = 1 to n – 1 )
f � v1n v11 � � 1
f � v im vim�1 � � 1 (i = 1 to n – 1 )
f � v mn v1m � � 1
Z4 Magic Labeling of Simple Graphs
f (vij vij�1 ) � 2 (i = 1 to n – 1 , j = 2 to m-1)
f (v nj v1j ) � 2 (j=2 to m-1)
f (vij vij�1 ) � 2 (i = 1 to n, j = 1 to m-1)
Then f+: V (G) � Z4 is defined as
f � � v11 � � f � v11 v1n � � f � v11 v12 � � f � v11 v12 �
f � � v1n � � f � v11 v1n � � f � v1n �1 v1n � � f � v1n v n2 �
f � � v1m � � f � v1m v nm � � f � v1m v 2m � � f � v1m v1m �1 �
f � � v mn � � f � v1m v mn � � f � v mn �1 v mn � � f � v nm v mn �1 �
f � � v1i � � f � v1i v1i �1 � � f � v1i �1 v1i � � f � v1i v i2 � ; i � 2 to n � 1
f � � v im � � f � v im vmi �1 � � f � v im�1 vim � � f � vim v im �1 � ; i � 2 to n � 1
f � � v ij � � f � vij vij�1 � � f � vij�1 v ij � � f � vij v ij�1 � � f � vij�1 vij � ; i � 2 to n � 1; j � 2 to m � 1
f � � v1j � � f � v1j v 2j � � f � v1j v nj � � f � v1j v1j�1 � � f � v1j�1 vij � ; j � 2 to m � 1
f � � v nj � � f � v nj v1j � � f � v nj �1 v nj � � f � v nj v nj�1 � � f � v nj�1 v nj � ; j � 2 to m � 1
j
Then we get f+ = � v i � � 0,
i = 1 to n and j = 1 to m.
f+ is constant and equal to 0.
Thus, f+ admits Z4 magic labeling and hence the generalised prism is Z4 magic.
Example 2.4. Z4 magic labeling of C4XP3 is given below.
Figure 2.2: Z4 Magic Labeling of C4XP 3
63
64
American Journal of Mathematical Science and Applications 2(1), 2014
Theorem 2.5
The Goldner Harary graph is Z4 magic.
Proof: Let G be a Goldner Harary graph.
V(G)= {v1,v2,……v11}
E(G)={v1,vi /i=2 to 7,10,11}U{v2,vi /i = 3,4,5,8 to11}U{v3,vi /i = 4 to 9}U{ v4,vi /i=7,8,11}
U{v5,vi /i = 6,9,10}
Define f: E (G) � Z4 – {0} as
f(v1,vi) = 2 (i=6,7,10,11)
f(v1,v2) = 3
f(v1,vi) =1 (i = 3,4,5)
f(v2,vi) = 2 (i = 3,8 to 11)
f(v2,vi) = 1 (i = 4, 5)
f(v3,vi) = 2 (i = 4 to 9)
f(v4,vi) = 2 (i = 7, 8, 11)
f(v5,vi) = 2 (i = 6, 9, 10)
Then f+ : V (G) � Z4 is defined as
f+ (v1) = �f(v1, vi);
i = 2 to 7,10,11
f+ (v2) = �f(v2, vi);
i = 1, 3, 4, 5, 8 to 11
f+ (v3) = �f(v3, vi);
i = 1, 2, 4 to 9
f+ (v4) = �f(v4, vi);
i = 1, 2, 3, 7, 8, 11
f+ (v5) = �f(v5, vi);
i = 1, 2, 3, 6, 9, 10
f+ (v6) = �f(v6, vi);
i = 1, 3, 5
f+ (v7) = �f(v7, vi);
i = 1, 3, 4
f+ (v8) = �f(v8, vi);
i = 2, 3, 4
f+ (v9) = �f(v9, vi);
i = 2, 3, 5
f+ (v10) = �f(v10, vi); i = 1, 2, 5
f+ (v11) = �f(v11, vi);
i = 1, 2, 4
Then we get f+ (vi) = 2; i = 1 to 11
f+ is constant and is equal to 2.
Therefore f+ admits Z4 magic labeling and hence the Goldner Harary graph is Z4 magic.
Example 2.6: Z4 magic labeling of Goldner Harary graph is given below.
Z4 Magic Labeling of Simple Graphs
65
Figure 2.3: Z4 Magic Labeling of Goldner Harary Graph
Theorem 2.7
The Herschel graph is Z4 magic.
Proof: Let G be a Herschel graph.
V(G) = {v1, v2……v11}
E(G) = {v1,vi /i = 4, 6, 7, 9} U {v2, vi /i = 6, 7, 10, 11}U{v3, vi /i = 4, 9, 10, 11}U{v5, vi /i = 4, 6, 10}
U{v8, vi /i = 7, 9, 11}
Define f: E (G) � Z4 – {0} as
f(v1, vi) = 2 (i = 4, 6, 7, 9)
f(v2, vi) = 3 (i = 6, 7, 10, 11)
f(v3, vi) = 3 (i = 4, 9, 10, 11)
f(v5, vi) = 3 (i = 4, 6, 10)
f(v8, vi) = 3 (i = 7, 9, 11)
Then f+ : V (G) � Z4 is defined as
f+ (v1) = �f(v1,vi)
i = 4, 6, 7, 11
f+ (v2) = �f(v2, vi)
i = 6, 7, 10, 11
f+ (v3) = �f(v3, vi)
i = 4, 9, 10, 11
f+ (v4) = �f(v4, vi)
i = 1, 3, 5
f+ (v5) = �f(v5, vi)
i = 4, 6, 10
f+ (v6) = �f(v6, vi)
i = 1, 2, 5
f+ (v7) = �f(v7, vi)
i = 1, 2, 8
66
American Journal of Mathematical Science and Applications 2(1), 2014
Then we get
f+ (v8) = �f(v8, vi)
i = 7, 9, 11
f+ (v9) = �f(v9, vi)
i = 1, 3, 8
f+ (v10) = �f(v10,vi)
i = 2, 3, 5
f+ (v11) = �f(v11, vi)
i = 2, 3, 8
f+ (vi) = 0
i = 1 to 11
f+ is constant and is equal to 0.
Therefore f+ admits Z4 magic labeling and hence the Herschel graph is Z4 magic.
Example 2.8. Z4 magic labeling of Herschel graph is given below
Figure 2.4: Z4 Magic Labeling of Herschel Graph
Theorem 2.9
The Grotzsch graph is Z4 magic.
Proof: Let G be a Grotzsch graph.
V(G) = {v1,v2,……v11}
E(G)={v1,vi /i = 2 to 6}U{ v7,vi /i=5,6,9,10}U{v8,vi /i=2,6,10,11}U{v9,vi /i=2,3,11}
U{v10, vi /i = 3, 4} U {v11, vi /i = 4, 5}
Define f: E (G) � Z4 – {0} as
f(v1,vi) = 2 (i = 2 to 6)
f(v7,vi) = 2 (i = 5, 6)
f(v8, vi) = 2 (i = 2, 6)
f(v9, vi) = 2 (i = 2, 3)
f(v10, vi) = 2 (i = 3, 4)
Z4 Magic Labeling of Simple Graphs
f(v11, vi) = 2 (i = 4, 5)
f(v7, vi) = 3 (i = 9, 10)
f(v8, vi) = 3 (i = 10, 11)
f(v9, v11) = 3
Then f+ : V (G) � Z4 is defined as
f+ (v1) = �f(v1, vi)
i = 2 to 6
f+ (v2) = �f(v2, vi)
i = 1, 8, 9
f+ (v3) = �f(v3, vi)
i = 1, 9, 10
f+ (v4) = �f(v4, vi)
i = 1, 10, 11
f+ (v5) = �f(v5, vi)
i = 1, 7, 11
f+ (v6) = �f(v6, vi)
i = 1, 7, 8
f+ (v7) = �f(v7, vi)
i = 5, 6, 9, 10
f+ (v8) = �f(v8, vi)
i = 2, 6, 10, 11
f+ (v9) = �f(v9, vi)
i = 2, 3, 7, 11
f+ (v10) = �f(v10, vi)
i = 3, 4, 7, 8
f+ (v11) = �f(v11, vi)
i = 4, 5, 8, 9
Then we get
f+ (vi) = 0
i = 1 to 11
f+ is constant and is equal to 0.
Therefore f+ admits Z4 magic labeling and hence the Grotzsch graph is Z4 magic.
Example 2.10. Z4 magic labeling of Grotzsch graph is given below
Figure 2.5: Z4 Magic Labeling of Grotzsch Graph
67
68
American Journal of Mathematical Science and Applications 2(1), 2014
Theorem 2.11
Let G be a fish graph then G is z4 magic.
Proof: Let G be a fish graph.
V(G) = {v1, v2…….v6}
E(G) = {vi vi+1 (i = 1 to 4), v5 v3, v3 v6, v6 v1}
Define f: E(G) � Z4-{0} as
f(vi vi+1) = 2,
i = 1 to 4
f(v5v3) = 2
f(v3v6) = 2
f(v6v1) = 2
Then define f+:V(G) � Z4 as
f+(v1) = f(v1v2) + f(v1v6)
f+(v2) = f(v1v2) + f(v2v3)
f+(v3) = f(v2v3) + f(v3v4) + f(v3v5) + f(v3v6)
f+(v4) = f(v3v4) + f(v4v5)
f+(v5) = f(v4v5) + f(v3v5)
f+(v6) = f(v5v6)+ f(v1v6)
We get
f+(vi) = 0 (i = 1 to 6)
f+ is constant and equal to 0
Therefore f+ admits Z4 magic labeling
Therefore Fish graph is a Z4 magic graph.
Example 2.12: Z4 magic labeling of Fish graph is given below.
Figure 2.6: Z4 Magic Labeling of Fish Graph
Z4 Magic Labeling of Simple Graphs
Theorem 2.13
Let G be a butterfly graph then G is z4 magic.
Proof: Let G be a butterfly graph.
V(G) = {v1, v2,……. v5}
E(G) = {vivi+1 (i = 1 to 4), v5 v3, v3 v1}
Define f: E(G) � Z4-{0} as
f(vivi+1) = 2, i = 1 to 4
f(v5v3) = 2
f(v3v1) = 2
Then define f+:V(G) � Z4 as
f+(v1) = f(v1v2)+ f(v1v3)
f+(v2) = f(v1v2)+ f(v2v3)
f+(v3) = f(v1v3)+ f(v2v3)+ f(v3v4)+ f(v5v3)
f+(v4) = f(v3v4)+ f(v4v5)
f+(v5) = f(v4v5)+ f(v3v5)
We get
f+(vi) = 0 (i = 1 to 5)
f+ is constant and equal to 0
Therefore f+ admits Z4 magic labeling
Therefore butterfly graph is Z4 magic graph.
Example 2.14: Z4 magic labeling of Butterfly graph is given below.
Figure 2.7: Z4 Magic Labeling of Butterfly Graph
69
70
American Journal of Mathematical Science and Applications 2(1), 2014
Theorem 2.15
Let G be a Octahedral graph then G is z4 magic.
Proof: Let G be a Octahedral graph.
V(G) ={v1, v2…….v6}
E(G) = {vivj (i, j = 1 to 6), i � j, j � 7-i}
Define f : E(G) � Z4 – {0} as
f(vivj) = 1, i, j = 1 to 6 i � j, j � 7–i
Then define f+ : V(G) ��Z4 as
f+(vi) = �f(vivj) i ��j, j � 7–i
We get
f+(vi) = 0 (i = 1 to 6)
f+ is constant and equal to 0
Therefore f+ admits Z4 magic labeling
Therefore Octahedral graph is Z4 magic graph.
Example 2.16: Z4 magic labeling of Octahedral graph is given below.
Figure 2.8: Z4 Magic Labeling of Octahedral Graph
Theorem 2.17
Let G be a Moser Spindle graph then G is z4 magic.
Proof: Let G be a Moser Spindle graph.
V(G) = {v1, v2…….v7}
E(G) = {v1v2, v1 v3, v1 v5, v6 v1, v2v3, v2 v4, v3 v4, v4 v7, v5v6, v5 v7, v6 v7}
Z4 Magic Labeling of Simple Graphs
Define f : E(G) � Z4-{0} as
f(v1vj) = 1, j = 2, 3, 5, 6
f(v2v3) = 2
f(v2v4) = 1
f(v3v4) = 1
f(v5v6) = 2
f(v4v7) = 2
f(v5v7) = 1
f(v6v7) = 1
Then define f+ : V(G) � Z4 as
f+(v1) = �f(v1vj)
j = 2, 3, 5, 6
f+(v2) = �f(v2vj)
j = 1, 3, 4
f+(v3) = �f(v3vj)
j = 1, 2, 4
f+(v4) = �f(v4vj)
j = 2, 3, 7
f+(v5) = �f(v5 vj)
j = 1, 6, 7
f+(v6) = �f(v6vj)
j = 1, 5, 7
f+(v7) = �f(v7vj)
j = 4, 5, 6
We get
f+(vi)= 0 (i=1 to 7)
f+ is constant and equal to 0
Therefore f+ admits Z4 magic labeling
Therefore Moser Spindle graph is Z4 magic graph.
Example 2.18: Z4 magic labeling of Moser Spindle graph is given below.
Figure 2.9: Z4 Magic Labeling of Moser Spindle Graph
71
72
American Journal of Mathematical Science and Applications 2(1), 2014
Note
In the above theorems if we multiply the edge labeling by a positive integer p, the vertex labeling remains to be a
constant and is equal to p times the constant value we obtained. Hence the above graphs admit Z4P magic labeling.
References
[1] A. Gutierez, A. Llado, “Magic coverings”, J. Combin. Math. Combin. Comput, 55, (2005), 43 -56.
[2] J. A. Galian, “A dynamic Survey of graph labeling”, Electronic Journal of Combinatorics, 17, (2012).
[3] F. Harary, “Graph Theory”, Addition – Wesley, Reading Mass, 1972.
[4] R. M. Low and S. M. Lee, “On group magic Eulerian graphs”, J. Combin. Math. Compin and Comput., 50,
(2004), 141-148.
© Copyright 2024 ExpyDoc
