Super \((a,d)\)-\(C_4\)-antimagicness of book graphs

1. Introduction

An edge-covering of finite and simple graph \(G\) is a family of subgraphs \(H_1, H_2, \dots, H_t\) such that each edge of \(E(G)\) belongs to at least one of the subgraphs \(H_i\), \(i=1, 2, \dots, t\). In this case we say that \(G\) admits an \((H_1, H_2, \dots, H_t)\)-(edge) covering. If every subgraph \(H_i\) is isomorphic to a~given graph \(H\), then the graph \(G\) admits an \(H\)-covering. A graph \(G\) admitting an \(H\)-covering is called \((a,d)\)-\(H\)-antimagic if there exists a total labeling \(f:V(G)\cup E(G) \to \{1,2,\dots, |V(G)|+|E(G)| \}\) such that for each subgraph \(H'\) of \(G\) isomorphic to \(H\), the \(H'\)-weights, $$wt_f(H')= \sum\limits_{v\in V(H')} f(v) + \sum\limits_{e\in E(H')} f(e),$$

constitute an~arithmetic progression \(a, a+d, a+2d,\dots , a+(t -1)d\), where \(a>0\) and \(d\ge 0\) are two integers and \(t\) is the number of all subgraphs of \(G\) isomorphic to \(H\). Moreover, \(G\) is said to be super \((a,d)\)-\(H\)-antimagic, if the smallest possible labels appear on the vertices. If \(G\) is a~(super) \((a,d)\)-\(H\)-antimagic graph then the corresponding total labeling \(f\) is called the (super) \((a,d)\)-\(H\)-antimagic labeling. For \(d=0\), the (super) \((a,d)\)-\(H\)-antimagic graph is called (super) \(H\)-magic.

The (super) \(H\)-magic graph was first introduced by Guti\'errez and Llad\'o in [1]. They proved that the star \(K_{1,n}\) and the complete bipartite graphs \(K_{n,m}\) are \(K_{1,h}\)-supermagic for some \(h\). They also proved that the path \(P_n\) and the cycle \(C_n\) are \(P_h\)-supermagic for some \(h\). Llad\'o and Moragas [2] investigated \(C_n\)-(super)magic graphs and proved that wheels, windmills, books and prisms are \(C_h\)-magic for some \(h\). Some results on \(C_n\)-supermagic labelings of several classes of graphs can be found in [3]. Maryati et al. [4] gave \(P_h\)-(super)magic labelings of shrubs, subdivision of shrubs and banana tree graphs. Other examples of \(H\)-supermagic graphs with different choices of \(H\) have been given by Jeyanthi and Selvagopal in [5]. Maryati et al. [6] investigated the \(G\)-supermagicness of a~disjoint union of \(c\) copies of a~graph \(G\) and showed that disjoint union of any paths is \(cP_h\)-supermagic for some \(c\) and \(h\).

The \((a,d)\)-\(H\)-antimagic labeling was introduced by Inayah et al. [7]. In [8] Inayah et al. investigated the super \((a,d)-H\)-antimagic labelings for some shackles of a~connected graph \(H\).

For \(H\cong K_2\), (super) \((a,d)\)-\(H\)-antimagic labelings are also called (super) \((a,d)\)-edge-an\-ti\-ma\-gic total labelings. For further information on (super) edge-magic labelings, one can see [9, 10, 11, 12].

The (super) \((a,d)\)-\(H\)-antimagic labeling is related to a~(super) \(d\)-antimagic labeling of type \((1,1,0)\) of a~plane graph which is the generalization of a~face-magic labeling introduced by Lih [13]. Further information on super \(d\)-antimagic labelings can be found in [14, 15, 16].

In this paper, we study the existence of super \((a,d)\)-\(C_4\)-antimagic labeling of book graphs.

2. Super \(C_4\)-antimagic labeling of book graphs and disjoint union of book graphs

In this section, we discuss super \((a,1)\)-\(C_4\)-antimagicness of {\it book graphs} for difference \(d=1\) and super \((b,0)\)-\(C_4\)-antimagicness of disjoint union of book graphs \(mB_n\) .

Let \(K_{1,n}\), \(n\geq2\) be a complete bipartite graph on \(n+1\) vertices. The {\it book graph} \(B_n\) is a cartesian product of \(K_{1,n}\) with \(K_2\).\ i.e., \(B_n \cong K_{1,n} \Box K_2\). Clearly book graph \(B_n\) admits covering by cycle \(C_4\).
The book graph \(B_n\) has the vertex and edge set $$V(B_n)=\{y_1,y_2\}\cup \cup_{i=1}^{n} \{x_{(1,i)}, x_{(2,i)}\}$$ $$E(B_n)=\cup_{i=1}^{n}\{y_1x_{(1,i)},y_2x_{(2,i)},x_{(1,i)}x_{(2,i)}\}\cup\{y_1y_2\}$$ respectively.

It can be noted that \(|V(B_n)|=2(n+1)\) and \(|E(B_n)|= 3n+1\).

Every \(C_4^{(j)}, 1\leq j\leq n \) in \(B_n\) has the vertex set: $$V(C_4^{(j)})=\{y_1, y_2, x_{(1,j)},x_{(2,j)}\}$$ and the edge set is: $$E(C_4^{(j)})=\{y_1y_2,y_1x_{(1,j)},y_2x_{(2,j)}, x_{(1,j)}x_{(2,j)}\}.$$ Under a total labeling \(\alpha\), the \(C_4^{(j)}\) weights, \(j=1,\dots, n\), would be:

Theorem 2.1. For any integer \(n\geq 2\), the book graph \(B_n\) is super \((a,1)\)-\(C_4\)-antimagic.

Proof. Under a labeling \(\alpha\), the set \(\{y_1,y_2, y_1y_2\}\), would be labeled as as: \begin{align*} \nonumber \alpha(y_1) &= 1, \ \ \ \ \ \alpha (y_2) = 2 \\ \alpha(y_1y_2) &= 2(n+1)+1, \end{align*} and therefore the partial sum of \(wt_\alpha(C_4^{(j)})\) would be

For remaining set of vertices and edges, the labeling \(\alpha\) is defined as:
\begin{align*} \alpha(x_{(t,i)})&= 2+j+(k-1)n, && {\text{if }} \ k=1, 2\\ &&&{\phantom{\text{if }}}\ j=1, 2, \dots, n\\ \alpha(x_{(1,i)}x_{(2,i)})&= 2(n+1)+1+j, && {\text{if }}\ j=1, 2, \dots, n\\ \alpha(y_kx_{(k,i)})&= (6-k)n+4-j, && {\text{if }} \ k=1, 2\\ &&&{\phantom{\text{if }}}\ j=1, 2, \dots, n \end{align*} Clearly $$\alpha(V(B_n))=\{1,2, \dots, 2(n+1)\}.$$ Therefore \(\alpha\) is a super labeling and together with $$\alpha(E(B_n))=\{2(n+1)+1, 2(n+1)+2,\dots, 5n+3\}$$ it shows \(\alpha\) is a total labeling.
Using (1) and (2), \(wt_\alpha(C_4^{(j)})\) are: \begin{align*} wt_\alpha(C_4^{(j)})&= 2(n+3) + (4+2i+n)+ (11n+11-j)\\ &= 14n+21+j. \end{align*} Thus \(wt_{\alpha}(C_4^{(j)})\) constitute an arithmetic progression with \(a=14n+22\) and \(d=1\). Hence book graphs are super \((a,1)\)-\(C_4\)-antimagic.
This completes the proof.

Theorem 2.2. For any integer \(n\geq 2\) and \(n\equiv 1\) (mod \(2\)), the book graph \(B_n\) is \(C_4\)-supermagic.

Proof. Under a labeling \(\psi\), the set \(\{y_1,y_2, y_1y_2\}\), would be labeled as as: \begin{align*} \nonumber \psi(y_1) &= 1, \ \ \ \ \ \psi (y_2) = 2 \\ \psi(y_1y_2) &= 2(n+1)+1, \end{align*} and therefore the partial sum of \(wt_\psi(C_4^{(j)})\) would be

For remaining set of vertices and edges, the labeling \(\psi\) is defined as: \begin{equation*} \psi(x_{(k,i)})=\begin{cases} 2+i, & \ k=1, i=1,2,\dots, n\\ 2n+3-i, & \ \ k=2, i=1,2,\dots, n\\ \end{cases} \end{equation*} \begin{equation*} \psi(x_{(1,i)}x_{(2,i)})=5n+4-i \end{equation*} \begin{equation*} \psi(y_kx_{(k,i)})=\begin{cases} 2n+3+\frac{i+1}{2} & \ k=1, i=1,3,\dots,n \\ \frac{5n+7}{2}+\frac{i}{2} & \ k=1, i=2,4,\dots,n-1, \\ \frac{7n+6+i}{2} & \ k=2, i=1,3,\dots,n\\ 3(n+1)+\frac{i}{2} & \ k=1, i=2,4,\dots,n-1 \end{cases} \end{equation*} Clearly $$\psi(V(B_n))=\{1,2, \dots, 2(n+1)\}.$$ Therefore \(\psi\) is a super labeling and together with $$\psi(E(B_n))=\{2(n+1)+1, 2(n+1)+2,\dots, 5n+3\}$$ it shows \(\psi\) is a total labeling.
Using (1) and (3), the \(wt_{\psi}C_4^{(j)}\) are: \begin{align*} wt_{\psi}(C_4^{(j)}) &= 2(n+3) + \left(\frac{11n+13}{2}+i\right)+(5n+4-i)+(2n+5)\\ &= \frac{29n+43}{2} \end{align*} Thus \(wt_{\psi}(C_4^{(j)})\) are independent of \(i\). Hence book graphs are \(C_4\)-supermagic for \(n\equiv 1\) (mod \(2\)). This completes the proof.

Theorem 2.3. Let \(m\geq 1, n\geq 2\) be positive integers and book graph \(B_n\) admits a \(C_4\)-supermagic labeling. Then the disjoint union of arbitrary number of copies of \(B_n\), i.e. \(mB_n\), also admits a \(C_4\)-supermagic labeling.

Proof. Let \(m\) be a positive integer. By the symbol \(x_i, i=1,2,\dots,m,\) we denote an element (a vertex or an edge) in the \(i^{\text th}\) copy of the book graph \(B_n\), denoted by \(B_n(i)\), corresponding to the element \(x\) in \(B_n\), i.e., \(x\in V(B_n) \cup E(B_n).\) Analogously, let \(C^j_{4}(i), i=1,2,\dots,m, \ j = 1,2,\dots,n ,\) be the subgraph in the \(i^{\text th}\) copy of \(B_n\) corresponding to the subgraph \(C^j_4\) in \(B_n\). Let us define the total labeling \(\phi\) of \(mB_n\) in the following way: \begin{equation*} \phi(x_i)=\begin{cases} m(\psi(x)-1)+i & \text{if}\,\, x \in V(B_n),\\ m\psi(x)+1-i & \text{if}\,\, x \in E(B_n). \end{cases} \end{equation*} First we shall show that the vertices of \(\bigcup_{i=1}^{m} B_n(i)\) under the labeling \(\phi\) use integers from \(1\) up to \(pm\), i.e. if \(i=1\) then the vertices of \(B_n(1)\) successively attain values \([1,m+1,2m+1,\dots, (p-1)m+1]\), if \(i=2\) then the vertices of \(B_n(2)\) successively assume values \([2,m+2,2m+2,\dots, (p-1)m+2],\dots,\) the values of vertices of \(B_n(i)\) are equal successively to \([i,m+i,2m+i,\dots, (p-1)m+i], \dots,\) if \(i=m\) then the vertices of \(B_n(m)\) successively assume values \([m,2m,3m, \dots,pm]\).
Second we can see that the edges of \(\bigcup_{i=1}^m B_n(i)\) under the labeling \(\phi\) use integers from \(pm+1\) up to \((p+q)m\). It means, if \(i=1\) then the edges of \(B_n(1)\) successively assume values \([(p+1)m, (p+2)m, (p+3)m, \dots, (p+q)m],\) if \(i=2\) then the edges of \(B_n(2)\) successively assume values \([(p+1)m-1, (p+2)m-1, (p+3)m-1, \dots, (p+q)m-1],\dots,\) the values of edges of \(B_n(i)\) are equal successively to \([(p+1)m+1-i, (p+2)m+1-i, (p+3)m+1-i, \dots, (p+q)m+1-i],\dots,\) if \(i=m\) then the edges of \(B_n(m)\) successively assume values \([pm+1, (p+1)m+1, (p+2)m+1, \dots, (p+q-1)m+1].\)
It is not difficult to see that the labeling \(\phi\) is a bijection between the integers \(\{1,2,\dots,(p+q)m\}\) and the vertices and edges of \(\bigcup_{i=1}^{m} B_n(i)\), therefore \(\phi\) is a total labeling.
Under the labeling \(\phi\), the weights of every subgraph \(C_4^{(j)}(i), 1\leq i\leq m, 1\leq j\leq k\), where \(k\) is the number of \(C_4\)'s in \(B_n(i)\), would be: \begin{equation*} \begin{split} wt_{\phi}(C_{(4,i)}^{(j)})= &\sum_{v\in V(C_4^{(j)}(i))}\phi(v)+\sum_{e\in E(C_4^{(j)}(i))}\phi(e)\\ =&\sum_{v\in V(C_4^{(j)}(i))}\left( m(\psi(v)-1)+i\right)+ \sum_{e\in E(C_4^{(j)}(i))}\left( m\psi(e)+1-i\right)\\ =& m \sum_{v\in V(C_4^{(j)}(i))} \psi(v)-m |V(C_4^{(j)}(i))|+i |V(C_4^{(j)}(i))| \end{split} \end{equation*} \begin{equation*} \begin{split} &+ m\sum_{e\in E(C_4^{(j)}(i))} \psi(e)+|E(C_4^{(j)}(i))|-i|E(C_4^{(j)}(i))|\\ =& m\left( \sum_{v\in V(C_4^{(j)}(i))} \psi(v) + \sum_{e\in E(C_4^{(j)}(i))} \psi(e)\right) - m |V(C_4^{(j)}(i))| +|E(C_4^{(j)}(i))|\\ & +i |V(C_4^{(j)}(i))|- i|E(C_4^{(j)}(i))| \\ =& m wt_{\psi}(C_4^{(j)}(i)) -m |V(C_4^{(j)}(i))| +|E(C_4^{(j)}(i))|+i|V(C_4^{(j)}(i))| - i|E(C_4^{(j)}(i))|. \end{split} \end{equation*} As every \(C_4^{(j)}(i)\), \(i=1,2,\dots, m, j=1,2,\dots, k\), is isomorphic to the cycle \(C_4\) it holds \begin{align*} |V(C_4^{(j)}(i))|&=|V(C_4)|=4,\\ |E(C_4^{(j)}(i))|&=|E(C_4)|=4. \end{align*} Thus for the \(C_4\)-weights we get \begin{align*} wt_{\phi}(C_4^{(j)}(i))&= m wt_{\psi}(C_4^{(j)})+ 4(1-m)\\ &= \frac{m}{2}(29n+43)+ 4(1-m)\\ &= \frac{m}{2}(29n+35)+ 4. \end{align*} It is easy to see that the set of all \(C_4^{(j)}(i)\)-weights in \(\bigcup_{i=1}^{m} B_n(i)\) consists of same integers. Thus the graph \(\bigcup_{i=1}^{m} B_n\) is a \(C_4\)-supermagic.
This completes the proof.

Competing Interests

The authors declare that they have no competing interests.

Acknowledgements

The authors are grateful for the valuable comments of the anonymous referees.