Magic graphs

INTRODUCTION TO MAGIC GRAPHS 

Definition 1.1 : Graph

A graph is a finite set of vertices and edges where every edge connects two vertices.

If G = G(V,E) is a graph, then V(G) is a finite non empty set of elements called vertices and E(G) is a set (possibly empty) of unordered pairs {u,v} of vertices u,v ε V (G) called edges.

The cardinality of the Vertex sex V(G) is called the order of G, commonly denoted by |V(G)|=v=p.

The cardinality of the edge set E(G) is the size of G denoted by    

  |E(G)|= e = q.

Example

                  

 

In the above graph |V(G)|=p=4. |E(G)|=q=2.

Definition 1.2: Labeling

A labeling for a graph is a map that takes graph elements to  alphabets or numbers (usually positive or non negative integers). Graph elements means Vertices and edges.

Examples:

Definition 1.3: Bijection

A function f: A→B is both 1-1 and onto then f is called a bijection.  In this case every element of B has exactly one pre-image in A.

Definition 1.4: 1-1

A function F:A →B is one-one (injective) if distinct elements in A have distinct images in B under F.  In other words f is 1-1 if X,Y, ε A and         X ≠ Y → f(x) ≠f(y) or equivalently f(x)=f(y) → x=y.

Definition 1.5: Onto

A function f:A→B is onto (surjective) if the range of f is equal to B.  Thus if F is onto, every element of B has a pre-image in A.

Definition 1.6: Magic Graph

A (p,q) graph G=(V,E) is said to be magic if there exist a bijection F:V∪E→{1,2,. …..,p+q} such that for all edges uv of G, f(u)+f(v)+f(uv) is constant.

Such a bijection is called a magic labeling of G. This is also called by edge magic labeling of G.  If Vertex magic, same property holds for vertices.

Examples:                            

f(u) + f(v) +f(uv)    = 9

f:{v1,v2,v3, u1,u2,u3} → {1,2,3,4,5,6}

f(u1)  = 1                       f(v1)  =  4

f(u2)  = 2                       f(v2)  =  5

f(u3)  = 3                       f(v3)  =  6

For the edge v2 →f(u1)+f(u3)+f(u1u3)= 1+3+5 = 9

For the edge v3 →f(u1)+f(u2)+f(u1u2)= 1+2+6 = 9

For the edge V1→f(u3)+f(u2)+f(u3u2)= 3+2+4 = 9

For any Magic labeling of G, there is a constant C(f) such that all the edges uv of G,

f(u) + f(v) + f(u v)  = c(f)

Example:

f:{u1,u1,u3,u4,v1,v2,v3,v4}→{1,2,3,4 ……9}

f(u1)=1                                    f(v1)=8

f(u2)=3                                    f(v2)=7

f(u3)=6                                    f(v3)=4

f(u4)=2                                    f(v4)=5

                                                f(v5)=9

In the above figure c (f)=12

Some examples for magic graph:

 c(f)=14

 

c(f)=21

 

c(f)=17

                            

Definition 1.7: Antimagic

 If there is a bijection f:V∪E→{1,2,3,….V+E} such that for all edges xy, f(s)+f(y)+f(xy) are all distinct, then G is called anti magic.

Example:

Definition 1.8:  Bipartite graph

A Graph G is called bigraph or bipartite graph if v can be partitioned into two disjoint subsets V₁ and V₂ such that every edge of G joins a point of V₁ to a point of V₁  to a point  of V₂  (V₁,V₂ ) is called a bipartition of G.

If further G contains every line joining the points of V₁ to the points of V₂ then G is called a complete bigraph.  If V₁ contains m points and V₂ contains n points then the complete bigraph G is denonted by K_m,n.

Example:

                               

                        bipartite graph

                      V1 contains 2 points

                      V2 contains 3 points

          

              

                  K_1,3                                                         K _3,3

Definition 1.9: Star

The graph K₁,m is called star, for m>,1.  In a star the vertices of maximum degree is called the centre of the star.

Example:

                                                  K_1,6                                 

V₁ is the centre of the above star

 Definition 1.10: Bistar

A bistar Bn,n is the graph obtained from K₂ by identifying a star K₁,m at each vertex of K₂.

Example: 

Definition 1.11: Complete Graph

A graph in which any two distinct points are adjacent is called a complete graph.  The complete graph with p points is denoted by K_p. K₃ is triangle.

Example:

 

  

                         

Definition 1.12: Degree

The degree of a point V₁ in a graph G is the number of lines incident with V₁.  The degree of V₁ is denoted by d_G(V₁) or deg(v₁) or simply d(v₁).

·        A point v of degree 0 is called an isolated point.

·        A point v of degree 1 is called an end point.

Example:

d(v1)=3

        d(v2)=d(v3)=d(v4)=1

        d(v5)=0.

Definition 1.13: Walk

A walk of a graph G is an alternating sequence of points and lines v_o,x₁,v₁,x₂,v₂ ……v_n-1,x_n,v_n  beginning and ending with points such that each line x_i is incident with v_i-1 and v_1.

The walk joins v_o and v_n and it is called a v_o - v_nwalk. V_o is called the initial point and v_n is called the terminal point of the walk.  The number of lines in the walk is called the length of the walk.

Definition 1.14: Path

A walk is called a path if all its points are distinct.

Example:

Definition 1.14: Cycle

A v_o-v_n walk is called closed if v₀=v_n.

A closed walk v_o,v₁,v₂ ……v_n,v_o in which n>3 and v_o,v₁,……v_n-1 are distinct is called a cycle of length n.

The graph consisting of a cycle of length n is denoted by C_n.

            C₃ is a triangle.

Example:

                                                      

Theorem 1.1:

If G is a magic graph and f is a magic labeling of G for which ther exists e€ E(u) such that f(e)=1.

Then G-e is magic.

Proof:

Let G(p,q) be Magic graph. And f is a magic labeling.

Let  f :V∪E→{1,2,…..p+q}.

Let  g: V(G) ∪ E(G)- {e} → {1,2,…..p+q-1}.

g(x) = f(x)-1. ∀ x ∈(v(G) ∪E(G)-{e}).

G is also Magic labeling. ∴ G-e is magic.

Hence proved.

Example:

         K₃

                       

                         

          

         c(f)=11                                               G-e such that f(e)=1

                                                                                                                             G-e                                                    c(f)=8

                                                                   G-e is also Magic.

                                                                                                         

References.

1   S.M. Hedge and Sudhakar shetty, On Magic graphs, Australian Journal of Combinatories 27 (2003), 277 – 284

2.   W.E. Wallies, E.T, Baskaro, M. Millar and slamin, Edge – Magic total labeling,Australian Journal of Combinatories

22 ( 2000), 177 -190.

3.   M.H. Gangadharappa and A.R. Desai, Graphs labeling on Magic & super magic graphs, J.Comp & Math. Sci.vol 2(2),(2011), 244 – 253.

4.   Selvan Avadayappan, R.Vasuki & P.Jeyanthi, Magic strength of a graph.  Indian Journal of Pure and applied Math., 31 (7), July 2000, 878 – 853.

5.   Daisy Cunninghans, Vertex –magicm furnian university, Electronic journal of under graduate mathematics, volume 9, 2004, 1-20.

6.   S. Arumugam and S. Ramachandran. Invitation to Graph theory, Scitech Publications (India) pvt.ltd., (2010)

7.   S. Arumugam and A.T. Isaac, Modern Alegebra, Scitech Publications (India ) pvt. Ltd., (2011).