On Super Edge-Magicness of Double Star

Stalin Kumar S

Easy Links

Research Article Open Access

On Super Edge-Magicness of Double Star

Stalin Kumar S*

Department of Mathematics, the American College, Madurai, Tamilnadu, India

*Corresponding author: Stalin Kumar S, Department of Mathematics, the American College, Madurai, Tamilnadu, India, 625 002, Tel: +919944035481; E-mail:

Received: July 25, 2018; Accepted: August 07, 2018; Published: August 13, 2018

Citation: Stalin Kumar S (2018) On Super Edge-Magicness of Double Star. J Comp Sci Appl Inform Technol. 3(2): 1-3. DOI: 10.15226/2474-9257/3/2/00133

Abstract

For a graph

G

, a bijection

f : V (G) \cup E (G) \to {1, 2, 3, \dots, p + q}

is called an edge-magic labeling of G if there exists a constant

s

such that

f (u) + f (u v) = s

, for any edge

(u, v) o f G

f

is said to be super edge-magic if

f (V (G)) = {1, 2, 3, \dots, p} .

After investigating the super edge-magicness of double stat

S_{m, n}

, a partial solution to a research problem (“For what

m

and

n

does

S_{m, n}

have an edge magic labeling?, stated by Marr and Wallis in [6]”) was given in this paper

Keywords: Graph labeling; Edge-magic graphs; Super edge-magic graphs;

AMS Mathematics Subject Classification:

05C78.

Introduction

In this paper we consider only finite and simple undirected graphs. The vertex and edge sets of a graph G are denoted by V(G) and E(G) respectively and we let |V(G)| = p and |E(G)| = q. For graph theoretic notations, we follow [1,2]. A labeling of a graph G is a mapping that carries a set of graph elements, usually vertices and/or edges into a set of numbers, usually integers. Many kinds of labeling have been studied and an excellent survey of graph labeling can be found in [4].

In 1998, Enomoto, et al. [3] introduced the concept of super edge-magic graphs. In 2005, Sugeng and Xie, [7] constructed some super edge-magic total graphs. The usage of the word “super” was introduced in [4]. A edge-magic total labeling is a bijection f from

V (G) \cup E (G)

to the integers {1,2,…,p+q} with the property that for every edge f(u) + f(v) + f(uv) = s for some constant s, such a labeling is (V )-super if f(V(G)) = {1,2,…,p}. A graph G is called edge-magic (resp. super edge-magic) if there exists an edge-magic (resp. super edge-magic) labeling of G.

Recently, Marimuthu and Balakrishnan, [5], introduced the notion of super edge-magic graceful graphs to solve some kind of network problems. A (p, q) graph G with p vertices and q edges is edge magic graceful if there exists a bijection f :

V (G) \cup E (G) \to {1, 2, \dots, p + q}

such that

| f (u) + f (v) - f (u v) | = k

, a constant for any edge uv of G. G is said to be super edge-magic graceful if f(V(G)) = {1,2,…,p}.

The double star

S_{m, n}

has two adjacent central vertices x and y. There are m leaves(vertices)

x_{1}, x_{2}, \dots, x_{m}

adjacent to x and n leaves(vertices)

y_{1}, y_{2}, \dots, y_{n}

adjacent to y. A (super) edgemagic total labeling of this graph can be specified by the list

({f (x_{1}), f (x_{2}), \dots, f (x_{m})}, f (x), f (y), {f (y_{1}), f (y_{2}), \dots, f (y_{n})}) .

One solution for

S_{2, 2}

to be edge-magic is ({8,11},2,5, {4,10}) with s = 16. One solution for

S_{2, 2}

to be super edge-magic is ({6,3},2,5, {4,1}) with s = 16.

Some existing results found in [6]

i. All Paths have edge-magic total labeling.
ii. A Cycle

C_{n}

is super edge-magic if and only if n is odd.
iii. The Complete bipartite graph

K_{m, n}

is super edge-magic if and only if

n = 1

m = 1.

In [6], Marr and Wallis quoted a research problem “For what m and n does

S_{m, n}

have an edge magic labeling?”. In this paper, we prove the following

i.

S_{n, n + 2}

is super edge-magic
ii.

S_{n, n}

is super edge-magic if n is even.

Main Result

In this section, we prove two main theorems.

Theorem 4.1: The double star

S_{n, n + 2}

is super edge-magic.

Proof: Let

G ≅ S_{n, n + 2}

has two adjacent central vertices x and y with n vertices

x_{1}, x_{2}, \dots, x_{n}

adjacent to

x

and

n + 2

vertices

y_{1}, y_{2}, \dots, y_{n + 2}

adjacent to

y

. Clearly

p = 2 n + 4

and

q = 2 n + 3

. Define a total labeling

f : V (G) \cup E (G) \to {1, 2, \dots, p + q}

f (x) = 2; f (y) = 4; f (y_{i}) = 2 i - 1

and

f (x_{j}) = 2 j + 4,

for all

1 \leq i \leq n + 2 a n d 1 \leq j \leq n .

Now the edges of G can be labeled as shown in Table 1 and Table 2.

Table 1: The edge label of

S_{n, n + 2}

whose

n + 2

edges are labeled

f	$y_{1}$	$y_{2}$	...	$y_{i}$	...	$y_{n + 1}$	$y_{n + 2}$
y	$4 n + 7$	$4 n + 5$		$4 n - (2 i - 9)$		$2 n + 7$	$2 n + 5$

Table 2: The edge label of

S_{n, n + 2}

whose

n

edges are labeled

f	$y_{1}$	$y_{2}$	...	$y_{i}$	...	$y_{n + 1}$	$y_{n + 2}$
x	$4 n + 4$	$4 n + 2$		$4 n - (2 i - 6)$		$2 n + 8$	$2 n + 6$

And

f (x y) = 4 n + 6

. It is easily seen that f is super edge-magic labeling with magic constant

s = 4 n + 12

. Hence the graph

S_{n, n + 2}

is super edge-magic. (Figure 1)

Figure 1: Super edge-magic labeling of

S_{3, 5}

with magic constant

s = 24

Theorem 4.2: The double star

S_{n, n}

is super edge-magic if n is even.

Proof: Let

G ≅ S_{n, n}

has two adjacent central vertices x and y with n vertices

x_{1}, x_{2}, \dots, x_{n}

adjacent to

x

and

n

vertices

y_{1}, y_{2}, \dots, y_{n}

adjacent to

y

. Clearly

p = 2 n + 4

and

q = 2 n + 3

. Define a total labeling

f : V (G) \cup E (G) \to {1, 2, \dots, p + q}

\begin{array}{l} f (y_{i}) = {\begin{matrix} i & i f & 1 \leq i \leq \frac{n}{2} \\ (\frac{n}{2} + 1) + i & i f & \frac{n}{2} + 1 \leq i \leq n \end{matrix}} \\ f (x_{i}) = {\begin{matrix} (\frac{n}{2} + 1) + i & i f & 1 \leq i \leq \frac{n}{2} \\ (n + 2) + i & i f & \frac{n}{2} + 1 \leq i \leq n \end{matrix}} \end{array}

f (x) = (\frac{n}{2} + 1) and f (y) = (\frac{n}{2} + 1) + (n + 1) .

Now the edges of G can be labeled as shown in Table 3 and Table 4.

Table 3: The edge label of

S_{n, n}

whose first

n

edges are labeled

$f$	$y$
$y_{1}$	$(3 n + 3) + (\frac{n}{2})$
$y_{2}$	$(3 n + 3) + (\frac{n}{2} - 1)$
. . .	. . .
$y_{j}$	$(3 n + 3) + (\frac{n}{2} + 1 - j)$
. . .	. . .
$y_{\frac{n}{2}}$	$(3 n + 3) + 1$
$y_{\frac{n}{2} + 1}$	$(2 n + 2) + (\frac{n}{2})$
. . .	. . .
$y_{k}$	$(2 n + 2) + (n + 1 - k)$
. . .	. . .
$y_{n - 1}$	$(2 n + 2) + 2$
$y_{n}$	$(2 n + 2) + 1$

Table 4: The edge label of

S_{n, n}

whose second

n

edges are labeled

$f$	$x$
$x_{1}$	$(\frac{7 n}{2} + 3) + (\frac{n}{2})$
$x_{2}$	$(\frac{7 n}{2} + 3) + (\frac{n}{2} - 1)$
. . .	. . .
$x_{j}$	$(\frac{7 n}{2} + 3) + (\frac{n}{2} + 1 - j)$
. . .	. . .
$x_{\frac{n}{2}}$	$(\frac{7 n}{2} + 3) + 1$
$x_{\frac{n}{2} + 1}$	$(\frac{5 n}{2} + 2) + (\frac{n}{2})$
. . .	. . .
$x_{k}$	$(\frac{5 n}{2} + 2) + (n + 1 - k)$
. . .	. . .
$x_{n - 1}$	$(\frac{5 n}{2} + 2) + 2$
$x_{n}$	$(\frac{5 n}{2} + 2) + 1$

f (x y) = 3 n + 3

It is easily seen that

f

is super edge-magic labeling with magic constant

s = 5 n + 6

. Hence the graph

S_{n, n}

is super edge-magic. (Figure 2)

Figure 2: Super edge-magic labeling of

S_{4, 4}

with magic constant

s = 24

Conclusion

In this paper, we had given two different solutions to a Research Problem given by Marr and Wallis in [6].

ReferencesTop