# ON SUPER EDGE-MAGIC TOTAL LABELING OF REFLEXIVE W-TREESi.

Byline: Muhammad Imran Mehar Ali Malik and M. Yasir Hayat Malik

ABSTRACT

Kotzig and Rosa [17] defined a magic labeling on a graph G to be a bijective mapping that assigns the integers from 1 to p+q to all the vertices and edges such that the sums of the labels on an edge and its two endpoints is constant for each edge. Ringel and Llado [20] redefined this type of labeling as edge-magic. Recently Enomoto et al. [6] introduced the name super edge-magic for magic labelings defined by Kotzig and Rosa with an additional property that the vertices receive the smallest labels. That is (V (G)) = {123...p}.

If the domain of a labeling is the set of all vertices and edges of the graph G then such labeling is called total labeling. The labelings which we study in this paper have another property that the weight (xy) xy E(G) calculated as; (xy) = (x) + (y) + (xy) is equal to a fixed constant k called the magic constant or sometimes the valence of . A graph is called super edge-magic total (SEMT) if it admits a super edge-magic total labeling. In this paper we construct new families of trees (using w-trees [15]) referred as reflexive w-trees and prove that they are super edge magic total. It is a classical problem to construct new classes of super edge magic total graphs using old ones.

Keywords: super edge magic total labeling w-trees reflexive w-trees.

INTRODUCTION AND PRELIMINARY RESULTS

Let G(VE) be a finite simple and undirected graph with |V (G)| = p and |E(G)| = q. Kotzig and Rosa [17] defined a magic labeling on a graph G to be a bijective mapping that

assigns the integers from 1 to p+q to all the vertices and edges such that the sums of the labels on an edge and its two endpoints is constant for each edge. Ringel and Llado [20] redefined this type of labeling as edge-magic. Recently Enomoto et al. [6] introduced the name super edge-magic for magic labelings defined by Kotzig and Rosa with an additional property that the vertices receive the smallest labels. That is (V (G)) = {123...p}.

If the domain of a labeling is the set of all vertices and edges of the graph G then such labeling is called total labeling. The labelings which we study in this paper have another property that the weight (xy) xy E(G) calculated as; (xy) = (x) + (y) + (xy) is equal to a fixed constant k called the magic constant or sometimes the valence of . A graph is called super edge-magic total (SEMT) if it admits a super edge-magic total labeling. Some labelings have only the vertex-set (edge-set) as their domain such labelings are called vertex-labelings (edge-labelings). Other domains for the labeling are also possible. There are many types of graph labelings for example harmonius cordial graceful equitable multilevel distance antimagic etc.

A number of classification problems on SEMT labelings of connected graphs have been investigated. Figueroa-Centeno et al. [8] proved the following:

If G is a bipartite or tripartite (super) edge-magic graph then nG is (super) edge-magic when n is odd.

If m is a multiple of n + 1 then K1 m K 1 n is super edge- magic.

K1 2 K1 n is super edge-magic if and only if n is a

multiple of 3.

Pm K1n is super edge-magic when m = 4.

2Pn is super edge-magic if and only if n is not 2 or 3.

K1m 2nK2 is super edge-magic for all m and n.

Figueroa-Centeno et al. [11] conjectured that Cm Cn is super edge-magic if and only if m+n = 9 and m+n is odd.

Baskoro and Ngurah [5] showed that nP3 is super edge- magic for n = 4 and n even. Lee and Kong [18] use the notation St(a1 a2 ...an ) to denote the disjoint union of the n stars St(a1) St(a2) ... St(an) of order a1+1 a2+1 ... an+1 respectively. They proved the following graphs to be super edge-magic: Equation

Lee and Kong in the same paper conjectured that St(a1 a2

... an) is super edge-magic when n(greater than 1) is odd. It is known that if a graph G(pq) is super edge-magic then q = 2p - 3 [6]. This bound can be improved for bipartite graphs of order p = 4 to be q = 2p-5 [19]. For more results concerning edge-magic total labelings see [4910] and a complete Gallian's survey paper [12]. Javaid et al. [15] studied the SEMT labeling of w-graph (W(n)) and w-tree (WT(nk)). They defined a w-graph W(n) to be a graph obtained by amalgamating a vertex from two stars 2St(n + 3).

In the proofs of the upcoming theorems the summation of type equation will be considered as 0. The theorems in this paper are proved using the lemma proposed by Figueroa et al. [7] stated below.

Equations

3 CONCLUDING REMARKS

In this paper we constructed new class of trees referred as reflexive w-trees. These graphs are constructed using w-trees introduced by Javaid et al. [10]. We studied the SEMT labeling of these graphs. It is an intresting and challenging

problem to study the SEMT labeling of trees due to the conjecture by Enomoto et al. [3] which states that all trees are super edge magic total. We invite the readers to investigate

The SEMT labeling of all trees and give a general proof.

The SEMT labeling of disjoint union of reflexive w-trees.

The SEMT labeling of disjoint union of stars and reflexive w-trees.

The SEMT labeling of one vertex amalgamation of k copies of reflexive w-trees.

REFERENCES

1. A. Ahmad K. Ali and E.T. Baskoro On super edge-magic total labeling of a forest of banana trees Utilitas Math.

to appear.

2. A. Ahmad I. Javaid and M. F. Nadeem Further results on super edge-magic deficiency of unicyclic graphs Ars Combin. 99(2011) 129-138.

3. A. Ahmad A. Q. Baig and M. Imran On super edge-

magicness of graphs Utilitas Math. 89(2012) 373-

380.

4. M. Baca Y. Lin and F. A. Muntaner-Batle Super edge-

antimagic labeling of path like-trees Util. Math.

73(2007) 117-128.

5. E. Baskoro and A. Ngurah On super edge-magic total

labelings Bull. Inst. Combin. Appl. 37(2003) 82-87.

6. H. Enomoto A. Llado T. Nakamigawa and G. Ringel

Super edge-magic graphs SUT J. Math. 34(1998) 105-

109.

7. R.M. Figueroa R. Ichishima and F.A. Muntaner-Batle

The place of super edge-magic labeling among other

classes of labeling Discrete Math. 231(2001) 153-168.

8. R. Figueroa-Centeno R. Ichishima and F. Muntaner-

Batle On edge-magic labelings of certain disjoint unions of graphs Australas. J. Combin. 32(2005) 225-

242.

9. R. M. Figueroa-Centeno R. Ichishima and F. Muntaner- Batle On super edge-magic graphs Ars Combin.

64(2002) 81-95.

10. R. M. Figueroa-Centeno R. Ichishima F. A. Muntaner- Batle and M. RiusFont Labeling generating matrices J. Combin. Math. Combin. Computing to appear.

11. R. Figueroa-Centeno R. Ichishima and F. Muntaner- Batle A magical approach to some labeling conjectures preprint.

12. J. A. Gallian A dynamic survey of graph labeling Electron. J. Combin. #DS6 16(2009).

13. M. Hussain K. Ali A. Razzaq Super edge-magic total labeling of a tree Utilitus Math. in press.

14. M. Hussain E.T. Baskoro Slamin On super edge magic

total labeling of banana trees Utilitus Math. in press.

15. M. Javaid M. Hussain K. Ali K.H. Dar Super edge- magic total labeling on w-trees Utilitas Math.

86(2011) 183191.

16. M. Javaid A. A. Bhatti M. Hussain K. Ali Super edge- magic total labeling on forest of extended w-trees Utilitas Math. in press.

17. A. Kotzig and A. Rosa Magic valuations of finite

graphs Canad. Math. Bull. 13(1970) 451-461. 65-80.

18. S. M. Lee and M. C. Kong On super edge-magic n-stars J. Combin. Math. Combin. Comput. 42(2002) 87-96.

19. F. A. Muntaner-Batle On magic graphs PhD Thesis (2001).

20. G. Ringel and A. S. Llado Another tree conjecture Bull.

ICA 18(1996) 83-85.