On super (a,d)-Cn-antimagic total labeling of disjoint union of cycles

Peer review under responsibility of Kalasalingam University.

Abstract

Let $H$ and $G$ be finite simple graphs where every edge of $G$ belongs to at least one subgraph that is isomorphic to $H$. An $(a,d)$-$H$-antimagic total labeling of a graph $G$ is a bijection $f:V\left(G\right)\cup E\left(G\right)\to \{1,2,\dots ,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\}$ such that for all subgraphs $H^{\prime }$ isomorphic to $H$, the $H$-weights, $w\left(H^{\prime }\right)={\sum }_{v\in V\left(H^{\prime }\right)}^{}f\left(v\right)+{\sum }_{uv\in E\left(H^{\prime }\right)}^{}f\left(uv\right)$ form an arithmetic progression $\{a,a+d,\dots ,a+(k-1)d\}$ where $a>0,d\ge 0$ are two fixed integers and $k$ is the number of subgraphs of $G$ isomorphic to $H$. Moreover, if the vertex set $V\left(G\right)$ receives the minimum possible labels $\{1,2,\dots ,\left|V\left(G\right)\right|\}$, then $f$ is called a super $(a,d)$-$H$-antimagic total labeling. In this paper we study super $(a,d)$-$C_n$-antimagic total labeling of a disconnected graph, namely $m{C}_n$.

Keywords:

• Super $(a,d)$-$H$-antimagic total labeling
• Disconnected graph
• Disjoint union of cycles

1 Introduction

Let $G$ and $H$ be finite, undirected and simple graphs. Let $V\left(G\right),V\left(H\right),E\left(G\right)$ and $E\left(H\right)$ be the vertex set of $G$, the vertex set of $H$, the edge set of $G$ and the edge set of $H$, respectively. Let $\left|V\left(G\right)\right|=p_G$, $\left|V\left(H\right)\right|=p_H$, $\left|E\left(G\right)\right|=q_G$ and $\left|E\left(H\right)\right|=q_H$. A graph $G$ admits an $H$-$covering$ if every edge of $G$ belongs to at least one subgraph $H^{\prime }$ that is isomorphic to $H$.

Gutiérrez and Lladó [1] defined an $H$-magic labeling of a graph as a generalization of a magic valuation by Kotzig and Rosa [2]. An $H$-magic total labeling of a graph $G$ admitting an $H$-covering is a bijection $f:V\left(G\right)\cup E\left(G\right)\to \{1,2,\dots ,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\}$ such that for all subgraphs $H^{\prime }$ isomorphic to $H$, $w\left(H^{\prime }\right)={\sum }_{v\in V\left(H^{\prime }\right)}^{}f\left(v\right)+{\sum }_{uv\in E\left(H^{\prime }\right)}^{}f\left(uv\right)$ is a constant. Moreover, if $f$ has an additional property $f\left(V\left(G\right)\right)=\{1,2,\dots ,\left|V\left(G\right)\right|\}$, then $f$ is called an $H$-supermagic total labeling. A graph $G$ that admits an $H$-(super)magic total labeling is called $H$-(super)magic.

Meanwhile, Simanjuntak, Bertault, and Miller [3] define an $(a,d)$-edge-antimagic total labeling for a graph $G(V,E)$ as a bijection $f$ from $V\left(G\right)\cup E\left(G\right)$ onto the set $\{1,2,\dots ,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\}$ such that the edge-weights $w\left(uv\right)$ defined by $w\left(uv\right)=f\left(u\right)+f\left(uv\right)+f\left(v\right)$, $uv\in E\left(G\right)$, constitute an arithmetic sequence $\{a,a+d,\dots ,a+(\left|E\left(G\right)\right|-1)d\}$ for some positive integers $a$ and $d$. Inspired by the two previous concepts, Inayah, Salman, and Simanjuntak [4] introduced an $(a,d)$-$H$-antimagic total labeling of a graph. Let $G$ be a graph that admits an $H$-covering. An $(a,d)$-$H$-antimagic total labeling of a graph $G$ is a bijection $f:V\left(G\right)\cup E\left(G\right)\to \{1,2,\dots ,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\}$ such that for all subgraphs $H^{\prime }$ isomorphic to $H$, the $H$-weights, $w\left(H^{\prime }\right)={\sum }_{v\in V\left(H^{\prime }\right)}^{}f\left(v\right)+{\sum }_{uv\in E\left(H^{\prime }\right)}^{}f\left(uv\right)$ form an arithmetic progression $\{a,a+d,\dots ,a+(k-1)d\}$ where $a>0,d\ge 0$ are two fixed integers and $k$ is the number of subgraphs of $G$ isomorphic to $H$. In this condition, $G$ is said to be $(a,d)$-$H$-antimagic. Particularly, if $f\left(V\left(G\right)\right)=\{1,2,\dots ,\left|V\left(G\right)\right|\}$, then $f$ is called a super $(a,d)$-$H$-antimagic total labeling. In this condition, $G$ is said to be super $(a,d)$-$H$-antimagic.

Many results about super $(a,d)$-$H$-antimagic total labeling have been found. For instances, in [5] Inayah et al. proved that shack $(H,k)$ is super $(a,d)$-$H$-antimagic. Laurence and Kathiresan [6] investigated super $(a,d)$-$P_h$-antimagic total labeling of stars. Susilowati et al. [7] studied super $(a,d)$-$C_n$-antimagic total labeling for ladder graph. Meanwhile, cycle-super antimagicness of tensor product of graphs has been studied by Purnapraja et al. [8].

In this paper we investigate the existence of super $(a,d)$-$C_n$-antimagic total labeling of one kind of disconnected graphs, namely the disjoint union of $m$ copies of cycles denoted by $m{C}_n$.

2 An upper bound of $d$ for super $(a,d)$-$H$-antimagic graphs

Lemma 1

Let $G$ and $H$ be graphs and let $k\ge 2$ be the number of subgraphs of $G$ that is isomorphic to $H$. If $G$ is super $(a,d)$- $H$-antimagic, then $d\le \frac{p_H(p_G-p_H)+q_H(q_G-q_H)}{k-1}$

Proof

Let $\left|V\left(G\right)\right|=p_G$, $\left|E\left(G\right)\right|=q_G$, $\left|V\left(H\right)\right|=p_H$ and $\left|E\left(H\right)\right|=q_H$. Since $G$ is super $(a,d)$-$H$-antimagic, the minimum $H$-weight is at least $1+2+\cdots +p_H+(p_G+1)+(p_G+2)+\cdots +(p_G+q_H)=\frac{p_H(p_H+1)}{2}+\frac{q_H\left((p_G+1)+(p_G+q_H)\right)}{2}$. Hence, (1) $a\ge \frac{p_H(p_H+1)+q_H((p_G+1)+(p_G+q_H))}{2}$(1) On the other hand, the maximum $H$-weight is at most $p_G+(p_G-1)+\cdots +(p_G-(p_H-1))+(p_G+q_G)+(p_G+q_G-1)+\cdots +(p_G+q_G-(q_H-1))=\frac{p_H(p_G+(p_G-(p_H-1)))}{2}+\frac{q_H((p_G+q_G)+(p_G+q_G-(q_H-1)))}{2}$. Therefore, (2) $\begin{array}{cc}\hfill a+(k-1)d\le & \frac{p_H(p_G+(p_G-(p_H-1)))}{2}+\hfill \\ \hfill & \frac{q_H((p_G+q_G)+(p_G+q_G-(q_H-1)))}{2}\hfill \end{array}$(2) By combining (⁽¹⁾(1) $a\ge \frac{p_H(p_H+1)+q_H((p_G+1)+(p_G+q_H))}{2}$(1) ⁽²⁾(2) $\begin{array}{cc}\hfill a+(k-1)d\le & \frac{p_H(p_G+(p_G-(p_H-1)))}{2}+\hfill \\ \hfill & \frac{q_H((p_G+q_G)+(p_G+q_G-(q_H-1)))}{2}\hfill \end{array}$(2) ), we obtain $(k-1)d\le p_H(p_G-p_H)+q_H(q_G-q_H)$Since $k\ge 2$, $d\le \frac{p_H(p_G-p_H)+q_H(q_G-q_H)}{k-1}\square$

3 Super $(a,d)$-$C_n$-antimagic total labeling of $m{C}_n$

In this section we present super $(a,d)$-$C_n$-antimagic total labeling of $m{C}_n$. Let $G\cong m{C}_n$ be the disjoint union of $m$ copies of $C_n$ with $V\left(G\right)=\left\{v_i^j\right|1\le i\le n,1\le j\le m\}$ and $E\left(G\right)=\left\{v_i^j{v}_{i+1}^j\right|1\le i\le n-1,1\le j\le m\}\cup \left\{v_n^j{v}_1^j\right|1\le j\le m\}$.

Observation 2

It follows from Lemma 1 that if $m{C}_n$ is super $(a,d)$- $C_n$-antimagic, where $m\ge 2$ and $n\ge 3$, then $d\le 2n^2$.

In the next theorem, we give a necessary condition for $m{C}_n$ to be super $(a,d)$-$C_n$-antimagic.

Theorem 3

For $m\ge 2,n\ge 3$, if $m{C}_n$ super $(a,d)$- $C_n$-antimagic, then

(i)	$d$ is odd and $m$ is odd, or

(ii)	$d$ is even and $m$ is arbitrary

Proof

Let $f:V\left(m{C}_n\right)\cup E\left(m{C}_n\right)\to \{1,2,\dots ,2mn\}$ be a super $(a,d)$-$C_n$-antimagic total labeling of $m{C}_n$. The sum of $C_n$-weights is $a+a+d+\cdots +(m-1)d$. On the other hand, in the computation of $C_n$-weights, the label of each vertex and edge of $G$ are counted once. Therefore, we obtain the following equation $\sum _{v\in V\left(m{C}_n\right)}^{}f\left(v\right)+\sum _{uv\in E\left(m{C}_n\right)}^{}f\left(uv\right)=\sum w\left(C_n\right)$ $\frac{mn(1+mn)}{2}+\frac{mn(mn+1+2mn)}{2}=\frac{m\left(a+a+(m-1)d\right)}{2}$ $a=n(2mn+1)-\frac{(m-1)d}{2}$ The value $a$ is an integer if and only if (i) $d$ is odd and $m$ is odd, or (ii) $d$ is even and $m$ is arbitrary.  □

In the following theorem we prove the existence of super $(a,d)$-$C_n$-antimagic total labeling of $m{C}_n$.

Theorem 4

$m{C}_n$ has a super $\left(n(2mn+1)-\frac{(m-1)d}{2},d\right)$- $C_n$-antimagic total labeling for $m\ge 2,n\ge 3,$ and $d\in \{0,2,4,\dots ,2n\}$

Proof

Define a total labeling $f:V\left(G\right)\cup E\left(G\right)\to \{1,2,\dots ,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\}$ in the following way.

For $d=0$

•	$f\left(v_i^j\right)=m(i-1)+j,\text{for}1\le i\le n\text{and}1\le j\le m$

•	$f\left(v_i^j{v}_{i+1}^j\right)=m(n+i)-j+1,\text{for}1\le i\le n-1\text{and}1\le j\le m$

•	$f\left(v_n^j{v}_1^j\right)=2mn-j+1,\text{for}1\le j\le m$

For $d=\{2,4,\dots ,2n-4\}$

•	$f\left(v_i^j\right)=m(i-1)+j,\text{for}1\le i\le n\text{and}1\le j\le m$

•	$f\left(v_i^j{v}_{i+1}^j\right)=\left\{\begin{array}{cc}m(n+i-1)+j,\hfill & \text{for}1\le i\le \frac{d}{2}\text{and}1\le j\le m\hfill \\ m(n+i)-j+1,\hfill & \text{for}\frac{d}{2}+1\le i\le n-1\text{and}1\le j\le m\hfill \end{array}\right.$

•	$f\left(v_n^j{v}_1^j\right)=2mn-j+1,\text{for}1\le j\le m$

For $d=2n-2$

•	$f\left(v_i^j\right)=m(i-1)+j,\text{for}1\le i\le n\text{and}1\le j\le m$

•	$f\left(v_i^j{v}_{i+1}^j\right)=m(n+i-1)+j,\text{for}1\le i\le n-1\text{and}1\le j\le m$

•	$f\left(v_n^j{v}_1^j\right)=2mn-j+1,\text{for}1\le j\le m$

For $d=2n$

•	$f\left(v_i^j\right)=m(i-1)+j,\text{for}1\le i\le n\text{and}1\le j\le m$

•	$f\left(v_i^j{v}_{i+1}^j\right)=m(n+i-1)+j,\text{for}1\le i\le n-1\text{and}1\le j\le m$

•	$f\left(v_n^j{v}_1^j\right)=m(2n-1)+j,\text{for}1\le j\le m$

Clearly, $f\left(V\left(G\right)\right)\in \{1,2,\dots ,\left|V\left(G\right)\right|\}$. Next, let $C_n^{\left(1\right)},C_n^{\left(2\right)},\dots ,C_n^{\left(m\right)}$ be the subgraphs of $G$ with $V\left(C_n^{\left(j\right)}\right)=\left\{v_i^j\right|1\le i\le n,1\le j\le m\}$ and $E\left(C_n^{\left(j\right)}\right)=\{v_i^j{v}_{i+1}^j|1\le i\le n-1,1\le j\le m\}\cup \left\{v_n^j{v}_1^j\right|1\le j\le m\}$. Then, consider the following cases for the $C_n$-weights as follows.

•	For $d=0$ It can be checked that for $1\le j\le m$, $w\left(C_n^{\left(j\right)}\right)={\sum }_{i=1}^{n}f\left(v_i^j\right)+{\sum }_{i=1}^{n-1}f\left(v_i^j{v}_{i+1}^j\right)+f\left(v_n^j{v}_1^j\right)=n(2mn+1)-\frac{(m-2j+1)d}{2}$

•	For $d=\{2,4,\dots ,2n-4\}$ It can be checked that for $1\le j\le m$, $w\left(C_n^{\left(j\right)}\right)={\sum }_{i=1}^{n}f\left(v_i^j\right)+{\sum }_{i=1}^{n-1}f\left(v_i^j{v}_{i+1}^j\right)+f\left(v_n^j{v}_1^j\right)=n(2mn+1)-\frac{(m-2j+1)d}{2}$

•	For $d=2n-2$ It can be checked that for $1\le j\le m$, $w\left(C_n^{\left(j\right)}\right)={\sum }_{i=1}^{n}f\left(v_i^j\right)+{\sum }_{i=1}^{n-1}f\left(v_i^j{v}_{i+1}^j\right)+f\left(v_n^j{v}_1^j\right)=n(2mn+1)-\frac{(m-2j+1)d}{2}$

•	For $d=2n$ It can be checked that for $1\le j\le m$, $w\left(C_n^{\left(j\right)}\right)={\sum }_{i=1}^{n}f\left(v_i^j\right)+{\sum }_{i=1}^{n-1}f\left(v_i^j{v}_{i+1}^j\right)+f\left(v_n^j{v}_1^j\right)=n(2mn+1)-\frac{(m-2j+1)d}{2}$

From all cases above, we can see that $w\left(C_n^{\left(j\right)}\right)$, $1\le j\le m$, build an arithmetic sequence with first term $a=n(2mn+1)-\frac{(m-1)d}{2}$ and common difference $d\in \{0,2,4,\dots ,2n\}$. Therefore, for $m\ge 2,n\ge 3,$ and $d\in \{0,2,4,\dots ,2n\}$, $m{C}_n$ has a super $\left(n(2mn+1)-\frac{(m-1)d}{2},d\right)$-$C_n$-antimagic total labeling.  □

Theorem 5

$m{C}_n$ has a super $\left((2n^2-n-1)m+2(n+1)-1,2n+2\right)$- $C_n$-antimagic total labeling for $m\ge 2,n\ge 3$

Proof

Define a total labeling $f:V\left(G\right)\cup E\left(G\right)\to \{1,2,\dots ,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\}$ in the following way.

For $m\ge 2$ and $n=3$

•	$f\left(v_i^j\right)=\left\{\begin{array}{cc}2\left(j+\lfloor \frac{i-1}{2}\rfloor (m-1)-1\right)+i,\hfill & \text{for}1\le i\le 2\text{and}1\le j\le m\hfill \\ 2m+j,\hfill & \text{for}i=3\text{and}1\le j\le m\hfill \end{array}\right.$

•	$f\left(v_i^j{v}_{i+1}^j\right)=m(i+2)+j,\text{for}1\le i\le 2\text{and}1\le j\le m$

•	$f\left(v_3^j{v}_1^j\right)=5m+j,\text{for}1\le j\le m$

For $m\ge 2,n>3$ and $n$ is odd

•	$f\left(v_i^j\right)=\left\{\begin{array}{cc}2\left(j+\lfloor \frac{i-1}{2}\rfloor (m-1)-1\right)+i,\hfill & \text{for}1\le i\le n-1\text{and}\hfill \\ \hfill & 1\le j\le m\hfill \\ m(n-1)+j,\hfill & \text{for}i=n\text{and}1\le j\le m\hfill \end{array}\right.$

•	$f\left(v_i^j{v}_{i+1}^j\right)=\left\{\begin{array}{cc}m(n+i-1)+j,\hfill & \text{for}1\le i\le \frac{n+3}{2}\text{and}1\le j\le m\hfill \\ m(n+i)-j+1,\hfill & \text{for}\frac{n+3}{2}+1\le i\le n-1\text{and}1\le j\le m\hfill \end{array}\right.$

•	$f\left(v_n^j{v}_1^j\right)=2mn-j+1,\text{for}1\le j\le m$

For $m\ge 2,n>3$ and $n$ is even

•	$f\left(v_i^j\right)=2\left(j+\lfloor \frac{i-1}{2}\rfloor (m-1)-1\right)+i,\text{for}1\le i\le n\text{and}1\le j\le m$

•	$f\left(v_i^j{v}_{i+1}^j\right)=\left\{\begin{array}{cc}m(n+i-1)+j,\hfill & \text{for}1\le i\le \frac{n+2}{2}\text{and}1\le j\le m\hfill \\ m(n+i)-j+1,\hfill & \text{for}\frac{n+2}{2}+1\le i\le n-1\text{and}1\le j\le m\hfill \end{array}\right.$

•	$f\left(v_n^j{v}_1^j\right)=2mn-j+1,\text{for}1\le j\le m$

Clearly, $f\left(V\left(G\right)\right)\in \{1,2,\dots ,\left|V\left(G\right)\right|\}$. Next, let $C_n^{\left(1\right)},C_n^{\left(2\right)},\dots ,C_n^{\left(m\right)}$ be the subgraphs of $G$ with $V\left(C_n^{\left(j\right)}\right)=\left\{v_i^j\right|1\le i\le n,1\le j\le m\}$ and $E\left(C_n^{\left(j\right)}\right)=\{v_i^j{v}_{i+1}^j|1\le i\le n-1,1\le j\le m\}\cup \left\{v_n^j{v}_1^j\right|1\le j\le m\}$. Then, we get the $C_n$-weights as follows.

•	For $m\ge 2$ and $n=3$ It can be checked that for $1\le j\le m$, $w\left(C_n^{\left(j\right)}\right)={\sum }_{i=1}^{n}f\left(v_i^j\right)+{\sum }_{i=1}^{n-1}f\left(v_i^j{v}_{i+1}^j\right)+f\left(v_n^j{v}_1^j\right)=(2n^2-n-1)m+2j(n+1)-1$

•	For $m\ge 2,n>3$ and $n$ is odd It can be checked that for $1\le j\le m$, $w\left(C_n^{\left(j\right)}\right)={\sum }_{i=1}^{n}f\left(v_i^j\right)+{\sum }_{i=1}^{n-1}f\left(v_i^j{v}_{i+1}^j\right)+f\left(v_n^j{v}_1^j\right)=(2n^2-n-1)m+2j(n+1)-1$

•	For $m\ge 2,n>3$ and $n$ is even It can be checked that for $1\le j\le m$, $w\left(C_n^{\left(j\right)}\right)={\sum }_{i=1}^{n}f\left(v_i^j\right)+{\sum }_{i=1}^{n-1}f\left(v_i^j{v}_{i+1}^j\right)+f\left(v_n^j{v}_1^j\right)=(2n^2-n-1)m+2j(n+1)-1$

$w\left(C_n^{\left(j\right)}\right)$, $1\le j\le m$, build an arithmetic sequence starting from $(2n^2-n-1)m+2(n+1)-1$ with difference $2n+2$. Therefore, the graph $m{C}_n$, for $m\ge 2,n\ge 3$, has a super $\left((2n^2-n-1)m+2(n+1)-1,2n+2\right)$-$C_n$-antimagic total labeling.  □

Theorem 6

$m{C}_n$ has a super $\left(n(2mn+1)-n^2(m-1),2n^2\right)$- $C_n$-antimagic total labeling for $m\ge 2,n\ge 3$

Proof

Define a total labeling $f:V\left(G\right)\cup E\left(G\right)\to \{1,2,\dots ,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\}$ in the following way.

•	$f\left(v_i^j\right)=n(j-1)+i,\text{for}1\le i\le n\text{and}1\le j\le m$

•	$f\left(v_i^j{v}_{i+1}^j\right)=n(m+j-1)+i,\text{for}1\le i\le n-1\text{and}1\le j\le m$

•	$f\left(v_n^j{v}_1^j\right)=n(m+j),\text{for}1\le j\le m$

Clearly, $f\left(V\left(G\right)\right)\in \{1,2,\dots ,\left|V\left(G\right)\right|\}$. Next, let $C_n^{\left(1\right)},C_n^{\left(2\right)},\dots ,C_n^{\left(m\right)}$ be the subgraphs of $G$ with $V\left(C_n^{\left(j\right)}\right)=\left\{v_i^j\right|1\le i\le n,1\le j\le m\}$ and $E\left(C_n^{\left(j\right)}\right)=\{v_i^j{v}_{i+1}^j|1\le i\le n-1,1\le j\le m\}\cup \left\{v_n^j{v}_1^j\right|1\le j\le m\}$. Then, we get the $C_n$-weights as follows. $\begin{array}{cc}\hfill w\left(C_n^{\left(j\right)}\right)& =\sum _{i=1}^{n}f\left(v_i^j\right)+\sum _{i=1}^{n-1}f\left(v_i^j{v}_{i+1}^j\right)+f\left(v_n^j{v}_1^j\right)\hfill \\ \hfill & =n(2mn+1)-n^2(m-2j+1)\hfill \end{array}$ $w\left(C_n^{\left(j\right)}\right)$, $1\le j\le m$, build an arithmetic progression $\{n(2mn+1)-n^2(m-1),n(2mn+1)-n^2(m-3),\dots ,n(2mn+1)-n^2(1-m)\}$. Therefore, the graph $m{C}_n$, for $m\ge 2,n\ge 3$, has a super $\left(n(2mn+1)-n^2(m-1),2n^2\right)$-$C_n$-antimagic total labeling.  □

Open Problem 1

For arbitrary $m\ge 2$ and $n\ge 3$, determine a super $(a,d)$- $C_n$-antimagic total labeling of $m{C}_n$ for the remaining even $d\in \{2n+4,2n+6,\dots ,2n^2-2\}$

Open Problem 2

For odd $m\ge 3$ and arbitrary $n\ge 3$, determine a super $(a,d)$- $C_n$-antimagic total labeling of $m{C}_n$ for odd $d\in \{1,3,\dots ,2n^2-1\}$

Notes

Peer review under responsibility of Kalasalingam University.