New classes of reverse super edge magic graphs

1.   Introduction

The edge magic labelings of graphs were introduced by Kotzig and A. Rosa ^[1] and they called also magic valuations of graphs. In ^[2], The super edge magic labelings of a graph then the idea of edge magic labelings is proved by H. Enomoto et al. In ^[8], R. M. Figueroa Centeno et al. proved all caterpillars are super edge magic also verified that $m{{K}_{1, n}}, m$ and $m, n$ are positive integers with the super edge magic is odd. In ^[4], M. Figueroa Centeno et al. defined that the forest ${{P}_{m}}\cup {{K}_{1, n}}, m\ge 4$ each positive integer $n\ge 1.$ All trees are edge magic is verified by G. Ringel and A. Llado ^[8]. H. Enomoto et al. proposed in ^[2] a more difficult hypothesis: that every tree is super edge magic. All the lobsters are gracefully demonstrated by J. C. Bermond ^[7].

If $G$ be the (super) 2-regular edge magic graph with $n$ positive integers, then $G\odot \overline{{{K}_{n}}}$ is (super) edge magic and therefore for every two integers $m\ge 3$ and $m\ge 1$, then $n-$ crown ${{C}_{m}}\odot {{\overline{K}}_{n}}$ is super edge magic these results proved by R. Figueroa Centeno et al. ^[6]. V. Yegnanarayanan ^[3] demonstrated that the graph is obtained through edge magic for $t\ge 2$ also introduced new pendant edges of the outermost ${{C}_{3}}$ in ${{P}_{t}}\times {{C}_{3}}$ at each vertex. In ^[10], The total graph $T\left({{P}_{n}} \right)$ is harmonious is obtained by R. Balakrishnan and R. Sampath kumar. In ^[2], H. Enomoto et al. is obtained that the complete bipartite graph ${{K}_{m, n}}$ is super edge-magic iff $m = 1$ or $n = 1.$ R. Balakrishnan et al. ^[11] obtained that the harmonious iff $n$ is even and the graph ${{K}_{2}}+2{{K}_{2}}$ is magic iff $n = 3.$ In ^[9], K. Kathiresan proved that the subdivision graph $S(L_{n})$ obtained by subdividing every edge of $G$ exactly one is graceful. In ^[5], V. Yegnanarayanan introduced several other variations of magic labelings and discuss what are called vertex-magic and vertex-antimagic of $(1, 1), (1, 0)$ and $(0, 1)$ graphs. Also, discussed edge-magic and edge-antimagic of $(1, 0)$ and $(0, 1)$ graphs. Finally, exhibited such magic, anti-magic labelings for a number of classes of graphs and derived several general results governing these graphs.

A reverse edge magic (REM) labeling of a graph $G(V, E)$ with $p$ vertices and $q$ edges is a bijection $f:V\left(G \right)\cup E\left(G \right)\to \{1, 2, \cdot \cdot \cdot, p+q\}$ such that $k = f\left(uv \right)-\{f\left(u \right)+f\left(v \right)\}$ is a constant $k$ for any edge $uv\in E\left(G \right).$ A REM labeling $f$ is called reverse super edge magic (RSEM) labeling if $f(V(G)) = \; \{1, 2, 3, 4, 5, \ldots, v\}$ and $f(E(G)) = \{v+1, v+2, v+3, v+4, v+5, \ldots, v+e\}.$ In this paper, we find some new classes of RSEM labeling and the investigation of the connection between the RSEM labeling and different classes of labeling.

Definition 1. Let $a$ be the path $P_{n}, \; 1 \leq i\leq n$ and $T_{1}$ be a caterpillar obtained by position one end vertex at each vertex. Let $T$ be the lobster created by linking a copy of $P_{2}$ at each end vertex $b_{i}$ of $1\leq i \leq n.$

2.   New structures of revese super edge magic graphs

The accompanying outcomes on trees give support to the conjecture that all trees are RSEM.

Lemma 1. A graph $G$ with $p$ vertices and $q$ edges is RSEM iff $\exists$ a bijective function $f:V(G)\rightarrow \{1, 2, ..., p\}$ so that the set $S = \{f(x)+f(y): xy \in E(G) \}$ contains $q$ number of successive numbers. In such a case, $f$ spreads to a RSEM labeling of the graph $G$ with reverse magic constant $k = p+q-s,$ where $s = max(S)$ and $S = \{(p+1)-k, (p+2)-k, (p+3)-k, ..., (p+q)-k\}.$

Theorem 1. If $m$ is odd. Then $3-$stat $S_{m, 3}$ is RSEM.

Proof. Let $m$ is odd. Assume $m$ be the degrees of vertex $x$ in $S_{m, 3}$ and $3$ is the length of $i^{th}$ path of $xu_{i}v_{i}w_{i}$ for $1 \leq i \leq m.$

The paths are RSEM and since $S_{1, 3}\cong P_{4},$ when $m = 1$ the outcome is true. Assume that $m$ is an odd number and $m > 3.$ Assume $n = 3m+1.$

Define the vertex labeling, $f:V(S_{m, 3})\rightarrow \{1, 2, 3, 4, 5, ..., n\}$ such that

Note that

is one set of $n-1$ successive integers. Accordingly, by using the Lemma 1, $f$ extend to a RSEM labeling of $S_{m, 3}$ with valence. $k = p+q-s = n+n-1+\frac{n+8}{3} = \frac{2n-5}{3},$ when $m \leq 3$ is odd.

Example 1. Figure 1 shows the RSEM labeling of the lobster $T$ with $n = 13.$

Theorem 2. The lobster $T$ characterized above is RSEM for total positive numbers $n > 3.$

Proof. We consider two cases.

Case 1: If $n$ is even.

Let $C_{i}$ denotes that the termination vertex of $T$ at $b_{i}, 1 \leq i \leq n.$

Characterize a vertex with labeling $f:V(T)\rightarrow \{1, 2, 3, ..., 3n\}$ such that

Therefore,

Accordingly, by using the Lemma 1, $f$ extend to a RSEM labeling of $T$ with valence $k = p+q-s = n+3.$

Example 2. Figure 2 shows the RSEM labeling of the lobster $T$ with $n = 11.$

Case 2: If $n$ is odd.

Define the vertex labeling $f:V(T)\rightarrow \{1, 2, 3, ..., 3n\}$ here

Since,

Accordingly, by using the Lemma $1, \; f$ extend to a RSEM labeling of $T$ with valence $k = p+q-s = 2n-1.$

Example 3. Figure 3 shows the RSEM labeling of the lobster $T$ with $n = 9.$

Definition 2. Let $\{a_{1}k_{1, n_{1}}, a_{2}k_{1, n_{2}}, ..., a_{p}k_{1, n_{p}}\}$ be a family of stars where $a_{i}k_{1, n_{i}},$ $a_{i}$ denotes the isomorphic disjoint copies of $k_{1, n_{i}}$ for $1 \leq i \leq p$ and $a_{i} \geq 1.$ Let $k_{1, n_{1}}$ and $v_{ijk}$ be the end vertices of $H_{ij}$ be the $j^{th}$ the isomorphic, $k = 1, 2, ..., n_{i}$ if one end vertex of each star which is adjacent to a vertex $w$ adjoin. Thus the trees subsequently defined by $H_{w}^{a_{1}+a_{2}+–+^{-}a_{p}}.$ These kinds of trees are prefers to as the banana tree.

Theorem 3. The banana tree $H_{w}^{a_{1}+a_{2}+–\mp a_{p}}$ corresponding to the family of stars $\{a_{1}k_{1, n_{1}}, a_{2}k_{1, n_{2}}, ..., a_{p}k_{1, n_{p}}\}, \; 1 < n_{1} < n_{2} < ... < n_{p}, p \geq 2$ and $a_{1}+a_{2}+...+a_{i} \geq n_{i}, i = 1, 2, ..., p$ is RSEM.

Proof. Conider the family of stars $\{a_{1}k_{1, n_{1}}, a_{2}k_{1, n_{2}}, ..., a_{p}k_{1, n_{p}}\}.$ Let $k_{1, n_{i}}, i = 1, 2, ..., p,$ is $H_{ij}$ be the $j^{th}$ the isomorphic copy. Assume $H_{ij}$ is the end-vertices of $v_{ijk}, k = 1, 2, 3, 4, ..., n_{i}$ and $u_{ij}$ be the $H_{ij}$ is center.

Let the new vertex be $w$ which is adjacent to one end vertex $v_{ij_{\beta_{ij}}}$ from every star $H_{ij}$ of the family where $\beta_{ij} = a_{0}+a_{1}+...+a_{i-1}+j$ and $a_{0} = 0.$ The new tree obtained is denoted by $H_{w}^{a_{1}+a_{2}+–\mp a_{p}}.$ and has $a_{1}(n_{1}+1)+a_{2}(n_{2}+1)+...+a_{p}(n_{p}+1)$ vertices and $a_{1}n_{1}+a_{2}n_{2}+...+a_{p}n_{p}+(a_{1}+a_{2}+...+a_{p})$ edges.

Let $p = a_{1}(n_{1}+1)+a_{2}(n_{2}+1)+...+a_{p}(n_{p}+1).$

Define a vertex labeling $f:V\Big(H_{w}^{a_{1}+a_{2}+–\mp a_{p}}\Big) \rightarrow \{1, 2, ..., p_{1}\}$, such that

Note that, $S = \{a_{1}n_{1}+a_{2}n_{2}+...+a_{p}n_{p}+2, a_{2}n_{2}+...+a_{p}n_{p}+3, ..., 2(a_{1}n_{1}+a_{2}n_{2}+...+a_{p}n_{p})+(a_{1}+...+a_{p})+1\}$.

Accordingly, by using the Lemma $1, \; f$ extend to a RSEM labeling of $H_{w}^{a_{1}+a_{2}+–\mp a_{p}}$ with valence $k = p+q-s = a_{0}+a_{1}+...+a_{p}.$

Definition 3. Consider the graph $G(t, m) = P_{1}\times C_{2m+1}$ where $x$ have $t$ vertices $(t \geq 2)$ is an odd cycle when the cartesian product of the path. Consider a new graph $G(t, m, n)$ by defining the new pendant edges $n$ at each vertex of the furthest odd numbered cycle in $G(t, m).$

Theorem 4. The graph $G(t, m, n)$ is RSEM, for $t \geq 2$ and $m \geq 2.$

Proof. Let $C_{2m+1}$ be the fixed vertex of innermost of $v_{11}$ and we will collect the different types of vertices $v_{12}, v_{13}, ..., v_{1(2m+1)}$ in clock-wise. For $2 \leq i \leq t,$ let $v_{i1}$ be the $i^{th}$ copy of $C_{2m+1}$ vertex was end to end to the vertex $v_{(i-1)(2m+1)}$ in the $(i-1)^{th}$ copy of $C_{2m+1}$ and take the other is adjacent to the vertex $v_{ijk}$ is the outermost $C_{2m+1}$ for $1 \leq k \leq n$ and $1 \leq j \leq (2m+1).$

Define the vertex marking $f:V(G(t, m, n))\rightarrow \{1, 2, ..., (2m+1)(t+n)\}$ such that

for $1 \leq i \leq t$ and $1 \leq j \leq (2m+1)$, $f(v_{ijk}) = (2m+1)(t+k-1)+(2m+2-j) \; for \; 1 \leq j \leq (2m+1) \; and \; 1 \leq k \leq n$.

Note that

is a set of all consecutive integers.

Accordingly, by using the Lemma $1, \; f$ extend to a RSEM labeling of $G(t, m, n)$ with valence $k = p+q-s = (2m+3)n+(2t+m), \; for \; t \geq 2 \; and \; m \geq 2.$

Example 4. Figure 4 shows the RSEM labeling of the graph $G(3, 2, 2)$ with $n = 22.$

Theorem 5. The graph $C_{n}\odot P_{2}$ is RSEM for all odd $n \geq 3.$

Proof. Let $n = 2m+1 \geq 3,$ here $n$ is an odd integer. Let $v_{1}, v_{2}, ..., v_{n}$ be the vertices of the cycle $C_{n}.$ Now $c_{n}\odot P_{2}$ is the graph defined by the attaching $P_{2}$ to every vertex of $C_{n}.$ Let the rim vertices $v_{i}$ of $C_{n}$ in $C_{n}\odot P_{2}$ is adjacent to the vertices $a_{i}, b_{i}, 1 \leq i \leq n.$ The graph $C_{n}\odot P_{2}$ has $3n$ vertices and $4n$ edges. Consider a labeling of vertex $f:V(C_{n}\odot P_{n}\rightarrow \{1, 2, ..., 3n\})$ such that

Define

is a set of $4n$ successive integers.

Accordingly, by using the Lemma $1, \; f$ extend to a RSEM labeling of $C_{n} \odot P_{2}$ with valence $k = p+q-s = \frac{15n-1}{2},$ when $n \geq 3$ is odd number.

Example 5. Figure 5 shows the RSEM labeling of the graph $C_{5}\odot P_{2}$ with $n = 12.$

Theorem 6. The graph $C_{n} \odot P_{3}$ is RSEM for every odd $n \geq 3.$

Proof. Let $C_{n}$ be an odd cycle with $n = 2m+1 \geq 3$ vertices. The cycle $C_{n}$ with the vertices $v_{1}, v_{2}, ..., v_{n}.$ Let the path of three vertices is $P_{3}.$ Now $4n$ vertices and $6n$ edges is a graph $C_{n} \odot P_{3}$ is obtained by attaching $P_{3}.$

Consider a vertex labeling $f:V(C_{n} \odot P_{3})\rightarrow \{1, 2, ..., 4n\}$ such that

If $n$ is odd, Then $m$ even for $f-$values and the rim vertices of $f-$values is $m+1$ odd. Let us the label $3n$ vertices outside the rim of $C_{n}$ in $C_{n} \odot P_{3}$ as follows. Let $u_{1}, u_{2}, ... u_{m},$ be the vertex degree two outside the rim, $f-$values are $2m, 2m-2, ..., 4, 2$ is adjacent to the rim vertices respectively. Again let $u_{n+1}, u_{n+2}, ... u_{n+m}$ be the remaining vertices of degree two, whose $f-$values are $2m, 2m-2, ..., 4, 2$ is adjacent to the rim vertices respectively. Let $u_{m+1}, u_{m+2}, ..., u_{n}$ be the vertex degree two outside the rim, whose $f-$values are $n, n-2, ..., 3, 1$ is adjacent to the rim vertices respectively. Also, let $u_{n+m+1}, u_{n+m+2}, ..., u_{2n}$ be the continuing vertex degree two outside the rim, whose $f-$values are $n, n-2, ..., 3, 1$ is adjacent to the rim vertices respectively. Let $u_{2n+1}.u_{2n+2}, ..., u_{2n+m+1}$ be the vertices of degree three outside the rim whose $f-$values are $n, n-2, ..., 3, 1$ is adjacent to the rim vertices respectively. Finally, let $u_{2n+m+2}, u_{2n+m+3}, ..., u_{3n}$ be the vertices of degree three whose $f-$values are $2m, 2m-2, ..., 4, 2$ is adjacent to the rim vertices respectively.

Consider $f(u_{i}) = n+i \; for \; 1 \leq i \leq 3n.$

Note that

is a set of all consecutive integers.

Accordingly, by using the Lemma $1, \; f$ extend to a RSEM labeling of $C_{n} \odot P_{3}$ with valence $k = p+q-s = \frac{7n-1}{2}.$

Example 6. Figure 6 shows the RSEM labeling of the graph $C_{7}\odot P_{3}$ with $n = 24.$

Definition 4. Let $L_{n}$ denote the ladder graph $P_{n}\times P_{2}$ and $L_{n} \odot K_{1}$ be the graph containing the connecting an edge at every vertex of $L_{n}.$

Theorem 7. The graph $L_{n} \odot K_{1}$ is RSEM for odd $n.$

Proof. Let $V((L_{n}) = \{u_{1}, u_{2}, ..., u_{n}; v_{1}, v_{2}, ..., v_{n}\}$ and $E((L_{n}) = \{u_{i}u_{i+1}, v_{i}v_{i+1}, u_{j}v_{j}, 1 \leq i \leq (n-1), 1 \leq j \leq n \}.$

Let $u_{i}^{1}$ and $v_{i}^{1}$ be the vertices is adjacent to the $u_{i}$ and $v_{i}$ respectively in $L_{n} \odot K_{1}.$ Then $V((L_{n} \odot K_{1}) = \{u_{i}, v_{i}, u_{i}^{1}, v_{i}^{1}:1 \ leq i \leq n, \}.$ and $V((L_{n} \odot K_{1}) = \{u_{i}u_{i+1}, v_{i}v_{i+1}, u_{j}v_{j}, u_{j}u_{j}^{1}, v_{j}v_{j}^{1}, 1 \leq i \leq (n-1), 1 \leq j \leq n \}.$ The graph $L_{n} \odot K_{1}$ has $4n$ vertices and $5n-2$ edges.

Define $f:V(L_{n} \odot K_{1})\rightarrow \{1, 2, ..., 4n\}$ is the vertex labeling where

Note that $S = \{f(x)+f(y):xy \in E(L_{n} \odot K_{1})\} = \{\frac{3n+5}{2}, \frac{3n+7}{2}, ..., \frac{13n-1}{2}\}$ is a set of alternative integers.

Accordingly, by using the Lemma $1, \; f$ extend to a RSEM labeling of $L_{n} \odot K_{1}$ with valence $k = p+q-s = \frac{5n-3}{2},$ for all odd $n.$ Accordingly, Lemma $1,$ if $G$ is a RSEM labeling of $(p, q)$ graph then $q \leq 2p-3.$

The next theorem gives a RSEM graph with $q = 2p-3.$

Example 7. Figure 7 shows the RSEM labeling of the graph $L_{5} \odot K_{1}$ with $n = 11.$

Theorem 8. The total graph $T(P_{n})$ is RSEM for every integer $n.$

Proof. Let $P_{n}$ be the path $u_{1}, u_{2}, ..., u_{n}$ and $e_{j}$ be the edge $u_{j}, u_{j+1}$ for $1 \leq j \leq (n-1).$ Then the vertex and edge set of $T(P_{n})$ as denoted as $V(T(P_{n})) = \{u_{j}, e_{j}:1 \leq j \leq n, 1 \leq j \leq (n-1).\}$

Note that $T(P_{n})$ has $2n-1$ vertices and $4n-5$ edges, then $q = 2p-3.$

Now define $f:V(T(P_{n}))\rightarrow \{1, 2, ..., (2n-1)\}$ as the vertex labeling such that

Since $S = \{f(x)+f(y):xy \in E(T(P_{n}))\} = \{3, 4, ..., (4n-3)\}$ is a set of successive integers.

Accordingly, by using the Lemma $1, \; f$ extend to a RSEM labeling of $T(P_{n})$ with valence $k = 2n-3.$

Example 8. Figure 8 shows the RSEM labeling of the graph $T(P_{4})$ with $n = 5.$

Theorem 9. The cycle graph $C_{n}$ with a chord of distance $3$ consisting two vertices is RSEM for each odd number $n,$ where $n > 7.$

Proof: Let $G$ be the graph and $C_{n}$ is a chord with consisting two vertices of $C_{n}(n \geq 7)$ at a distance $3.$ Let $(G) = \{v_{1}, v_{2}, ..., v_{n}\},$ join the vertices $v_{1}$ and $v_{n-2}$ as a chord for $G$ so that $d(v_{1}, v_{n}) = 3.$ Note that $G$ has $n$ vertices and $n+1$ edges. Define $f:V(G)\rightarrow \{1, 2, ..., n\}$ the vertex labeling such that

Note that $S = \{f(x)+f(y):xy \in E(G)\} = \{\frac{n+1}{2}, \frac{n+3}{2}, ..., \frac{3n+1}{2}\}$ is a set of successive integers.

Accordingly, by using the Lemma $1, \; f$ extend to a RSEM labeling of $G$ with valence $k = p+q-s = \frac{n+1}{2}.$

Example 9. Figure 9 shows the RSEM labeling of the graph $C_{7}$ with $n = 4.$

Theorem 10. Let $G_{1}, G_{2}, ..., G_{m}$ be $m$ disconnect and $n$ cycles having vertex sets $v_{i} = \{v_{1}^{i}, v_{2}^{i}, ..., v_{n}^{i}\}, \; i = 1, 2, ..., m$ here $n$ is odd and $n \geq 3.$ Let $G$ the graph attained by connecting $v_{n}^{1}$ to $v_{j}^{2}, 1 \leq j \leq n$ and $v_{n}^{k}$ to $v_{j}^{k+1}, 1 \leq j \leq n, 2 \leq j \leq (m-1).$ Then $G$ is a RSEM graph.

Proof. The graph $G$ has containing $mn$ vertices and $n(2m-1)$ edges.

Consider $f:V(G)\rightarrow \{1, 2, ..., mn\}$ a vertex labeling such that

$f(v_{i}^{1}) = \begin{cases} \frac{i+1}{2}, & if \; i \; is \; odd, 1 \leq i \leq n\\ \frac{n+1+i}{2}, & if \; i \; is \; even, 1 \leq i \leq n \end{cases}$

$f(v_{i}^{r}) = 5r-4,$ if $2 \leq r \leq m$

$f(v_{i}^{r}) = \begin{cases} f(v_{1}^{r})+\frac{i-1}{2}, & if \; i \; is \; odd, 1 \leq i \leq n, 2 \leq r \leq m \\ f(v_{n}^{r})+\frac{i}{2}, & if \; i \; is \; even, 2 \leq i \leq n, 2 \leq r \leq m. \end{cases}$

It is easy to see that $S = \{f(x)+f(y):xy \in E(G)\} = \{\frac{n+3}{2}, \frac{n+5}{2}, ..., n+10m-7\}$ is a set of $n(2m-1)$ successive integers.

Accordingly, by using the Lemma $1, \; f$ extend to a RSEM labeling of $G$ with valence $k = p+q-s = n(3m-2)-10m+7.$

Example 10. Figure 10 shows the RSEM labeling of the graph $G_{1}$ with $n = 4.$

3.   Conclusions

Permitting to the outcome and argument we establish reverse edge magic valuation of the 3-star $S_{m, 3}$ if $m$ is odd, the lobster $T$ characterized above is RSEM for all integers $n > 3,$ the banana tree $H_{w}^{a_{1}+a_{2}+–+a_{p}}.$ for $t \geq 2$ and $m \geq 2$ the graph $G(t, m, n)$ the graphs $C_{n} \odot P_{2}, C_{n} \odot P_{3}$ for all odd $m \geq 3,$ the graph $L_{n} \odot K_{1}$ for odd $n,$ the total graph $T(P_{n})$ for any positive integer $n$ and the graph $C_{n}$ is a cycle with a chord conncection two vertices at the distance of $3$ units for all odd $n, \; n > 7.$