Super (a,d)-edge antimagic total labeling of a subclass of trees

Peer review under responsibility of Kalasalingam University.

Abstract

A graph labeling is a mapping that assigns numbers to graph elements. The domain can be the set of all vertices, the set of all edges or the set of all vertices and edges. A labeling in which domain is the set of vertices and edges is called a total labeling. For a graph $G$ with the vertex set $V\left(G\right)$ and the edge set $E\left(G\right)$, a total labeling $f:V\left(G\right)\cup E\left(G\right)\to \{1,2,3,\dots ,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\}$ is called an $(a,d)$-edge antimagic total labeling if the set of edge weights $\{f\left(x\right)+f\left(xy\right)+f\left(y\right):xy\in E\left(G\right)\}$ forms an arithmetic progression with initial term $a$ and common difference $d$. An $(a,d)$-edge antimagic total labeling is called a super $(a,d)$-edge antimagic total labeling if the smallest labels are assigned to the vertices. In this paper, we investigate the super $(a,d)$-edge-antimagic total labeling of a subclass of trees called subdivided stars for all possible values of $d$, mainly $d=1,3$.

Keywords:

• Super $(a,d)$-EAT labeling
• Stars
• Subdivided stars

1 Introduction

Let $G=(V\left(G\right),E\left(G\right))$ be a graph with $\left|V\left(G\right)\right|=v$ and $\left|E\left(G\right)\right|=e$, where $V\left(G\right)$ and $E\left(G\right)$ are the vertex set and the edge set of the graph $G$, respectively. All the graphs in this paper are finite, simple and undirected. A general reference for graph-theoretic ideas can be seen in [1].

Motivated by the concept of the magic squares in number theory, Sadláček [2] introduced the notion of a magic labeling. He defined a graph to be magic if it has an edge labeling with range of real numbers such that the sum of the labels of the incident edges on a vertex remains constant for each vertex of the graph. Stewart [3] defined that a magic labeling of the graph $G$ is a super magic labeling if the edge labels are consecutive integers. A bijective mapping $f:V\left(G\right)\cup E\left(G\right)\to \{1,2,3,\dots ,v+e\}$ is called an edge magic total labeling (EMT) of the graph $G$ if $f\left(x\right)+f\left(xy\right)+f\left(y\right)=k$, where $k$ is a constant, independent of the choice of the edge $xy\in E\left(G\right)$. The subject of the edge magic total (EMT) labeling of graphs has its origin in the works of Kotzig and Rosa [4,5]. Enomoto et al. [6] defined the concept of a super edge magic total (SEMT) labeling. They defined that an edge magic total (EMT) labeling of the graph $G$ is called a super edge magic total (SEMT) labeling if the vertices receive the smallest labels.

Hartsfield and Ringel [7] introduced the concept of an antimagic labeling. In their terminology, a graph $G$ is called antimagic if its edges are labeled with the labels $\{1,2,3,\dots ,e\}$ in such a way that all vertex-weights are pairwise distinct, where a vertex-weight of a vertex $v$ is the sum of labels of all the edges which are incident to $v$.

Definition 1.1

[8]

An $(s,d)$-edge-antimagic vertex ($(s,d)$-EAV) labeling of a graph $G$ is a bijective function $f:V\left(G\right)\to \{1,2,\dots ,v\}$ such that the set of edge sums of all edges in $G$, $\{w\left(xy\right)=f\left(x\right)+f\left(y\right):xy\in E\left(G\right)\}$, forms an arithmetic progression $\{s,s+d,s+2d,\dots ,s+(e-1)d\}$, where the minimum edge sum $s>0$ and the common difference $d\ge 0$ are two fixed integers.

Definition 1.2

[8,9]

An $(a,d)$-edge-antimagic total ($(a,d)$-EAT) labeling of a graph $G$ is a bijective function $f:V\left(G\right)\cup E\left(G\right)\to \{1,2,\dots ,v+e\}$ such that the set of edge weights of all edges in $G$, $\{w\left(xy\right)=f\left(x\right)+f\left(xy\right)+f\left(y\right):xy\in E\left(G\right)\}$, forms an arithmetic progression $\{a,a+d,a+2d,\dots ,a+(e-1)d\}$, where the minimum edge weight $a>0$ and the common difference $d\ge 0$ are two fixed integers. If such a labeling exists then $G$ is said to be an $(a,d)$-EAT graph.

Definition 1.3

[8]

An $(a,d)$-EAT labeling of a graph $G$ is called a super $(a,d)$-edge-antimagic total (super $(a,d)$-EAT) labeling if $f\left(V\left(G\right)\right)=\{1,2,\dots ,v\}$. If such a labeling exists then $G$ is called a super $(a,d)$-EAT graph.

Simanjuntak et al. [9,10] defined the concept of an $(a,d)$-edge antimagic total ($(a,d)$-EAT) labeling of a graph $G$. Notice that an $(a,0)$-EAT labeling is an EMT labeling and a super $(a,0)$-EAT labeling is a SEMT labeling of the graph $G$. Thus, an $(a,d)$-EAT labeling and a super $(a,d)$-EAT labeling are natural extensions of the notion of EMT labeling defined by Kotzig and Rosa in [4,5] and the notion of the SEMT labeling which is defined by Enomoto et al. in [6], respectively.

Enomoto et al. [6] proposed the conjecture that every tree admits a super $(a,0)$-EAT labeling. In an effort of attacking this conjecture, many authors have proved the existence of a super $(a,0)$-EAT labeling for different classes of trees, for example banana trees [11], $w$-trees [12], path like trees [13] caterpillars [14], subdivided caterpillar [15], subdivided stars [16], disjoint union of caterpillars [17] and union of stars [18]. For more study, we refer [8,19,20]. Lee and Shan [21] verified this conjecture for trees with at most 17 vertices by the help of a computer. However, this conjecture is still an open problem.

In particular, Simanjuntak et al. [9] proved that $C_{2n}$ has $(2n+2,1)$-EAT and $(4n+2,2)$-EAT labelings, $C_{2n+1}$ has $(3n+4,3)$-EAT and $(3n+5,3)$-EAT labelings, $P_{2n}$ has $(6n,1)$-EAT and $(6n+2,2)$-EAT labelings, and $P_{2n+1}$ has $(3n+4,2)$-EAT, $(3n+4,3)$-EAT and $(2n+4,4)$-EAT labelings. Ngurah [22] proved that every odd cycle $C_{2k+1}$ has $(4k+4,2)$-EAT and $(4k+5,2)$-EAT labelings. Kavitha et al. [23] proved that the extended duplicate graph of path admits $(a,d)$-EAT for the certain values of $a$ and $d$.

Moreover, a super $(a,0)$-EAT labeling for the subdivision of the star $K_{1,3}$ is proved by Ngurah et al. [24]. Furthermore, Salman et al. [25] investigated a super $(a,0)$-EAT labeling for the graphs $S_n^1$ and $S_n^2$, where $S_n^1$ and $S_n^2$ are obtained by the insertion of one and two vertices in the each edge of the star $K_{1,n}$, respectively. Later on, Javaid et al. [26] and Akhlaq et al. [27] proved the super $(a,d)$-EAT labeling for the subdivided stars $T(n_1,n_2,n_3,\dots ,n_p)$ (see, Definition 1.4) under certain conditions on $n_i$, where $1\le i\le p$ and $d=0,2$. However, the investigation of the super $(a,d)$-EAT labeling for the subdivided stat $T(n_1,n_2,n_3,\dots ,n_p)$ is still open with different values of $n_i$, where $1\le i\le p$.

In the continuation of this study, this paper deals with the more generalized classes of the subdivided stars which admit a super $(a,d)$-EAT labeling for $d=0,2$. In addition, we also find some classes which admit a super $(a,d)$-EAT labeling for $d=1$ and $d=3$.

Definition 1.4

Let $n_i$ and $p$ be integers satisfying the conditions $n_i\ge 1$ and $p\ge 3$, where $1\le i\le p$. Then, the graph $G\cong T(n_1,n_2,n_3,\dots ,n_p)$ is obtained by paths of lengths $n_1,n_2,n_3,\dots ,n_p$ all sharing one end vertex. The vertex set and the edge set of the subdivided star $G$ are $V\left(G\right)=\left\{c\right\}\cup \left\{x_i^{l_i}\right|1\le l_i\le n_i;1\le i\le p\}$ and $E\left(G\right)=\left\{c{x}_i^1\right|1\le i\le p\}\cup \left\{x_i^{l_i}{x}_i^{l_i+1}\right|1\le i\le p;1\le l_i\le n_i-1\}$, respectively. Thus $v=\left|V\left(G\right)\right|=1+\sum _{i=1}^p{n}_i\text{and}e=\left|E\left(G\right)\right|=v-1\text{.}$ Note that the graph $T\underset{p\text{-}\mathrm{times}}{\underbrace{(1,1,1,\dots ,1)}}$ is a star $K_{1,p}$.

2 A few known lemmas

In this section, we recall some important lemmas which are frequently used in the main results.

The following lemma appeared in [19] and provides an upper bound for the feasible values of $d$.

Lemma 2.1

If a $(v,e)$-graph is a super $(a,d)$-EAT then $d\le \frac{2v+e-5}{e-1}$.

Since, for any tree graph, we have $v=e+1$, it follows that $d\le 3$. Consequently, $0\le d\le 3$. Therefore, in the present study, we prove the existence of the super $(a,d)$-EAT labeling of the different classes of the subdivided stars for $d=0,1,2,3$.

In the following lemma, Bača et al. [28] investigated the relationship between an $(s,d)$-EAV labeling and a super $(a,d)$-EAT labeling.

Lemma 2.2

If a $(v,e)$-graph $G$ has an $(s,d)$-EAV labeling then $G$ admits

(i)	a super $(s+v+e,d-1)$-EAT labeling,

(ii)	a super $(s+v+1,d+1)$-EAT labeling.

Ngurah et al. [24] and Salman et al. [25] found upper and lower bounds of the minimum edge weight $a$ for two different classes of the subdivided stars which are stated as follows:

Lemma 2.3

If $T(n_1,n_2,n_3)$ is a super $(a,0)$-EAT graph, then $\frac{1}{2l}(5l^2+3l+6)\le a\le \frac{1}{2l}(5l^2+11l-6)$, where $l={\sum }_{i=1}^3{n}_i$.

Lemma 2.4

If $T(n,n,\dots ,n)$ is a super $(a,0)$-EAT graph, then $\frac{1}{2l}(5l^2+(9-2n)l+n^2-n)\le a\le \frac{1}{2l}(5l^2+(2n+5)l+n-n^2)$, where $l=n^2$.

Furthermore, for $d=0$ Javaid [29] and for $d\in \{0,1,2,3\}$ Javaid and Akhlaq [30] proved the following lemmas on the upper and lower bounds of the minimum edge weight $a$ of the more generalized class of the subdivided stars denoted by $T(n_1,n_2,n_3,\dots ,n_p)$, where $n_i>1$ are integers for $1\le i\le p$.

Lemma 2.5

If $T(n_1,n_2,n_3,\dots ,n_p)$ is a super $(a,0)$-EAT labeling, then $\frac{1}{2l}(5l^2+(9-2p)l+p(p-1))\le a\le \frac{1}{2l}(5l^2+(5+2p)l-p(p-1))$, where $l={\sum }_{i=1}^p{n}_i$.

Lemma 2.6

If $T(n_1,n_2,n_3,\dots ,n_p)$ is a super $(a,d)$-EAT labeling, then $\frac{1}{2l}(5l^2+p^2-2lp+9l-p-(l-1)ld)\le a\le \frac{1}{2l}(5l^2-p^2+2lp+5l+p-(l-1)ld)$, where $l={\sum }_{i=1}^p{n}_i$ and $d\in \{0,1,2,3\}$.

3 Main results

In this section, we present the main results related to the super $(a,d)$-EAT labeling of the different classes of the subdivided stars for all possible values of $d$.

3.1 Super $(a,d)$-EAT labeling for $d=0,2$

In Theorems 3.1.1 and 3.1.2, we study two different classes of the subdivided stars for the existence of a super $(a,0)$-EAT labeling and a super $(a,2)$-EAT labeling under certain conditions, mainly for even $k\ge 2$ and odd $k\ge 3$. Moreover, Theorem 3.1.2 deals with a class of the subdivided stars which is a generalization of the class found in [27].

Theorem 3.1.1

Let $k$, $n$ and $p$ be integers satisfying the conditions $k\ge 2$ is even, $n\ge 3$ is odd and $p\ge 5$, then $G\cong T(kn,kn-1,kn-1,kn-1,n_5,\dots ,n_p)$ admits a super $(a,0)$-EAT labeling and a super $(a^{\prime },2)$-EAT labeling, where $n_m=(kn-1)+(kn-2)(2^{m-4}-1)$ for $5\le m\le p$.

Proof

Let $v=\left|V\left(G\right)\right|$, then $v=2(2kn-1)+\sum _{m=5}^p[(kn-1)+(kn-2)(2^{m-4}-1)]\text{.}$ Define the vertex labeling $f:V\left(G\right)\cup E\left(G\right)\to \{1,2,3,\dots ,v+e\}$ as $f\left(c\right)=3kn+\frac{1}{2}\sum _{m=5}^p[kn+(kn-2)(2^{m-4}-1)]\text{.}$ When odd $1\le l_i\le n_i$: for $1\le i\le 4$,$f\left(x_i^{l_i}\right)=\{\begin{array}{cc}\frac{l_1+1}{2}\text{,}& \text{for}{x}_1^{l_1}\text{,}\\ kn-\frac{l_2-1}{2}\text{,}& \text{for}{x}_2^{l_2}\text{,}\\ (kn+1)+\frac{l_3-1}{2}\text{,}& \text{for}{x}_3^{l_3}\text{,}\\ 2kn-\frac{l_4-1}{2}\text{,}& \text{for}{x}_4^{l_4}\text{,}\end{array}$ and for $5\le i\le p$, $f\left(x_i^{l_i}\right)=2kn+\frac{1}{2}\sum _{m=5}^p[kn+(kn-2)(2^{m-4}-1)]-\frac{l_i-1}{2}\text{.}$ When even $2\le l_i\le n_i$ and $\alpha =2kn+\frac{1}{2}{\sum }_{m=5}^p[kn+(kn-2)(2^{m-4}-1)]$: for $1\le i\le 4$,$f\left(x_i^{l_i}\right)=\{\begin{array}{cc}\alpha +\frac{l_i}{2}\text{,}& \text{for}{x}_1^{l_1}\text{,}\\ (\alpha +kn-1)-\frac{l_2-2}{2}\text{,}& \text{for}{x}_2^{l_2}\text{,}\\ (\alpha +kn+1)+\frac{l_{3-2}}{2}\text{,}& \text{for}{x}_3^{l_3}\text{,}\\ (\alpha +2kn-2)-\frac{l_4-2}{2}\text{,}& \text{for}{x}_4^{l_4}\text{,}\end{array}$ and for $5\le i\le p$, $f\left(x_i^{l_i}\right)=(\alpha +2kn-2)+\frac{1}{2}\sum _{m=5}^p[(kn-2)+(kn-2)(2^{m-4}-1)]-\frac{l_i-2}{2}\text{.}$ Using the above vertex labeling, we have the set of edge sums $\{f\left(x\right)+f\left(y\right):xy\in E\left(G\right)\}=\{s,s+d,s+2d,\dots ,s+(e-1)d\}=\{\alpha +2,\alpha +3,\dots ,(\alpha +1)+e\}$, where $e=v-1$. Thus, $f$ is an $(s,d)$-EAV labeling with $s=\alpha +2$ and $d=1$. Now, by Lemma 2.2, $f$ can be extended to a super $(a,0)$-EAT labeling with minimum edge weight $a=s+v+e=v+e+(2kn+2)+\frac{1}{2}{\sum }_{m=5}^p[kn+(kn-2)(2^{m-4}-1)]=(2v+2kn+1)+\frac{1}{2}{\sum }_{m=5}^p[kn+(kn-2)(2^{m-4}-1)]$ and a super $(a^{\prime },2)$-EAT labeling with minimum edge weight $a^{\prime }=s+v+1=(v+2kn+3)+\frac{1}{2}{\sum }_{m=5}^p[kn+(kn-2)(2^{m-4}-1)]$. □

Theorem 3.1.2

Let $k$, $n$ and $p$ be integers satisfying the conditions $k\ge 3$ is odd, $n\ge 3$ is odd and $p\ge 6$, then $G\cong T(2kn,kn,kn,kn,kn,n_6,\dots ,n_p)$ admits a super $(a,0)$-EAT labeling and a super $(a^{\prime },2)$-EAT labeling, where $n_m=kn+(kn-1)(2^{m-5}-1)$ for $6\le m\le p$.

Proof

Let $v=\left|V\left(G\right)\right|$, then $v=(6kn+1)+\sum _{m=6}^p[kn+(kn-1)(2^{m-5}-1)]\text{.}$ Define the vertex labeling $f:V\left(G\right)\cup E\left(G\right)\to \{1,2,3,\dots ,v+e\}$ as $f\left(c\right)=(5kn+2)+\frac{1}{2}\sum _{m=6}^p[(kn+1)+(kn-1)(2^{m-5}-1)]\text{.}$ When odd $1\le l_i\le n_i$: for $1\le i\le 5$, $f\left(x_i^{l_i}\right)=\{\begin{array}{cc}\frac{l_1+1}{2}\text{,}& \text{for}{x}_1^{l_1}\text{,}\\ (kn+1)+\frac{l_2-1}{2}\text{,}& \text{for}{x}_2^{l_2}\text{,}\\ (2kn+1)-\frac{kn-l_3}{2}\text{,}& \text{for}{x}_3^{l_3}\text{,}\\ (2kn+2)+\frac{l_4-1}{2}\text{,}& \text{for}{x}_4^{l_4}\text{,}\\ (3kn+2)-\frac{kn-l_5}{2}\text{,}& \text{for}{x}_5^{l_5}\text{,}\end{array}$ and for $6\le i\le p$, $f\left(x_i^{l_i}\right)=(3kn+2)+\frac{1}{2}\sum _{m=6}^p[(kn+1)+(kn-1)(2^{m-5}-1)]-\frac{l_i-1}{2}\text{.}$ When even $2\le l_i\le n_i$ and $\alpha =(3kn+2)+\frac{1}{2}{\sum }_{m=6}^p[(kn+1)+(kn-1)(2^{m-5}-1)]$: for $1\le i\le 5$, $f\left(x_i^{l_i}\right)=\{\begin{array}{cc}\alpha +\frac{l_i}{2}\text{,}& \text{for}{x}_1^{l_1}\text{,}\\ \alpha +kn+\frac{l_2}{2}\text{,}& \text{for}{x}_2^{l_2}\text{,}\\ \alpha +2kn-\frac{l_3}{2}\text{,}& \text{for}{x}_3^{l_3}\text{,}\\ \alpha +2kn+\frac{l_4}{2}\text{,}& \text{for}{x}_4^{l_4}\text{,}\\ \alpha +3kn+\frac{l_5}{2}\text{,}& \text{for}{x}_5^{l_5}\text{,}\end{array}$ and for $6\le i\le p$, $f\left(x_i^{l_i}\right)=(\alpha +3kn)+\frac{1}{2}\sum _{m=6}^p[(kn-1)+(kn-1)(2^{m-5}-1)-\frac{l_i}{2}\text{.}$ Using the above vertex labeling, we have the set of edge sums $\{f\left(x\right)+f\left(y\right):xy\in E\left(G\right)\}=\{s,s+d,s+2d,\dots ,s+(e-1)d\}=\{\alpha +2,\alpha +3,\dots ,(\alpha +1)+e\}$, where $e=v-1$. Thus, $f$ is an $(s,d)$-EAV labeling with $s=\alpha +2$ and $d=1$. Now, by Lemma 2.2, $f$ can be extended to a super $(a,0)$-EAT labeling with minimum edge weight $a=s+v+e=(2v+3kn+4)+\frac{1}{2}{\sum }_{m=6}^p[(kn+1)+(kn-1)(2^{m-5}-1)]$ and a super $(a^{\prime },2)$-EAT labeling with minimum edge weight $a^{\prime }=s+v+1=(v+3kn+5)+\frac{1}{2}{\sum }_{m=6}^p[(kn+1)+(kn-1)(2^{m-5}-1)]$. □

3.2 Super $(a,d)$-EAT labeling for $d=1,3$

In this subsection, we present the results related to a super $(a,1)$-EAT labeling and a super $(a^{\prime },3)$-EAT labeling for two different classes of the subdivided stars.

Theorem 3.2.1

Let $k$, $n$ and $p$ be integers satisfying the conditions $k\ge 1$, $n\ge 3$ is odd, and $p\ge 4$, then $G\cong T(2kn,kn,kn+1,n_4,\dots ,n_p)$ admits a super $(a,1)$-EAT labeling and a super $(a^{\prime },3)$-EAT labeling, where $n_m=kn+1+(kn+1)(2^{m-3}-1)$ for $4\le m\le p$.

Proof

Let $v=\left|V\left(G\right)\right|$, then $v=2kn+2+\sum _{m=4}^p[kn+1+(kn+1)(2^{m-3}-1)]\text{.}$ Define the vertex labeling $f_1:V\left(G\right)\to \{1,2,3,\dots ,v\}$ as follows: $f\left(c\right)=2kn+1\text{.}$ When $1\le l_i\le n_i$: for $1\le i\le 3$, $f_1\left(x_i^{l_i}\right)=\{\begin{array}{cc}2kn-(l_1-1)& \text{for}{x}_1^{l_1}\text{,}\\ 2kn+1+l_2\text{,}& \text{for}{x}_2^{l_2}\text{,}\\ 4kn+2-(l_3-1)\text{,}& \text{for}{x}_3^{l_3}\text{,}\end{array}$ and for $4\le i\le p$, $f_1\left(x_i^{l_i}\right)=4kn+2+\sum _{m=4}^p[kn+1+(kn+1)(2^{m-3}-1)]-(l_i-1)\text{.}$ From the above vertex labeling, we have the set of edge sums $\{f_1\left(x\right)+f_1\left(y\right):xy\in E\left(G\right)\}=\{s,s+d,s+2d,\dots ,s+(e-1)d\}=\{3,3+2,3+4,\dots ,3+(e-1)2\}$, where $e=v-1$. Thus, $f_1$ is an $(s,d)$-EAV labeling with $s=3$ and $d=2$. Now, by Lemma 2.2(i), $f_1$ can be extended to a super $(a,1)$-EAT labeling with $a=2(v+1)$. Similarly, by Lemma 2.2(ii), $f_1$ can be extended to a super $(a^{\prime },3)$-EAT labeling with $a^{\prime }=v+4$.

Theorem 3.2.2

Let $k$, $n$ and $p$ be integers satisfying the conditions $k\ge 1$ is even, $n\ge 3$ is odd, and $p\ge 4$, then $G\cong T(kn,kn-1,kn,n_4,\dots ,n_p)$ admits a super $(a,1)$-EAT labeling and a super $(a^{\prime },3)$-EAT labeling, where $n_m=kn+(2^{m-3}-1)kn$ for $4\le m\le p$.

Proof

Let $v=\left|V\left(G\right)\right|$, then $v=3kn+\sum _{m=4}^p[kn+(2^{m-3}-1)kn]\text{.}$ Define the vertex labeling $f_2:V\left(G\right)\to \{1,2,3,\dots ,v\}$ as follows: $f_2\left(c\right)=kn+1\text{.}$ For $1\le l_i\le n_i$ and $1\le i\le p$, we define $f_2\left(x_i^{l_i}\right)=f_1\left(x_i^{l_i}\right)\text{.}$ From the above vertex labeling, we have the same set of edge sums as in Theorem 3.2.1. Consequently, $f_2$ is an $(s,d)$-EAV labeling with $s=3$ and $d=2$. Then, by Lemma 2.2$f_2$ is a super $(a,1)$-EAT labeling with $a=2(v+1)$ and a super $(a^{\prime },3)$-EAT labeling with $a^{\prime }=v+4$. □

Notes

Peer review under responsibility of Kalasalingam University.