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) → Nq = {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) → Nq × 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 (ej), g(ej)) if and only if f (e) ≤ f (ej). This relation ≤ is a partial order on the range of l. Let {(f (e1), g(e1)), (f (e2), g(e2)), . . . , (f (ek), g(ek))} be a chain in the range of l. We define a product of the elements of this chain as follows: k (f (ei), g(ei)) := ((((g(e1) ∗ g(e2)) ∗ g(e3)) ∗ · · · ) ∗ g(ek). 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 (e1), g(e1)) ≤ (f (e2), g(e2)) ≤ · · · ≤ (f (en), g(en)). We define n l∗(u) := (f (ei), g(ei)). 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 S3 and investigate graphs that are S3-magic.