ON THE S3-MAGIC GRAPHS

Abstract

Let G = (V (G), E(G)) be a finite (p, q) graph and let (A, ∗) be a finite non-abelain group with identity element 1.  Let  f  :  E(G)  → N_q  =  {1, 2, . . . , q} and let g : E(G) → A \ {1} be two edge labelings of G such that f is bijective. Using these two labelings f and g we can define another edge labeling l : E(G) → N_q × A \ {1} by l(e) := (f (e), g(e))  for all e ∈ E(G). Define a relation ≤ on the range of l by: (f (e), g(e)) ≤ (f (e^j), g(e^j))  if and only if    f (e) ≤ f (e^j).  This relation ≤ is a partial order on the range of l. Let {(f (e₁), g(e₁)), (f (e₂), g(e₂)), . . . , (f (e_k), g(e_k))} be a chain in the range of l. We define a product of the elements of this chain as follows: k (f (e_i), g(e_i)) := ((((g(e₁) ∗ g(e₂)) ∗ g(e₃)) ∗ · · · ) ∗ g(e_k). i=1 Let u ∈ V and let N ^∗(u) be the set of all edges incident with u. Note that the restriction  of  l  on  N ^∗(u)  is  a  chain,  say  (f (e₁), g(e₁))  ≤ (f (e₂), g(e₂))  ≤ · · · ≤ (f (e_n), g(e_n)). We define  n l^∗(u) :=        (f (e_i), g(e_i)). i=1  If l^∗(u) is a constant, say a for all u V (G), we say that the graph G is A - magic. The map l^∗ is called an A -magic labeling of G and the corresponding constant a is called the magic constant. In this paper, we consider the permutation group S₃ and investigate graphs that are S₃-magic.