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

Author(s): Muhammad Awais Umar1, Malik Anjum Javed2, Mujtaba Hussain3, Basharat Rehman Ali1
1Abdus Salam School of Mathematical Sciences, Government College University, Lahore Pakistan.
2Department of Mathematics, Government. M.A.O College, Lahore Pakistan.
3Department of Mathematics, COMSATS Institute of Information & technology, Lahore, Pakistan.
Copyright © Muhammad Awais Umar, Malik Anjum Javed, Mujtaba Hussain, Basharat Rehman Ali. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Let \(G=(V,E)\) be a~finite simple graph with \(|V(G)|\) vertices and \(|E(G)|\) edges. An edge-covering of \(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\). If every subgraph \(H_i\) is isomorphic to a given graph \(H\), then the graph \(G\) admits an \(H\)-covering. A graph \(G\) admitting \(H\) covering is called an \((a,d)\)-\(H\)-antimagic if there is a bijection \(f:V\cup E \to \{1,2,\dots, |V(G)|+|E(G)| \}\) such that for each subgraph \(H’\) of \(G \) isomorphic to \(H\), the sum of labels of all the edges and vertices belonged to \(H’\) constitutes an arithmetic progression with the initial term \(a\) and the common difference \(d\). For \(f(V)= \{ 1,2,3,\dots,|V(G)|\}\), the graph \(G\) is said to be super \((a,d)\)-\(H\)-antimagic and for \(d=0\) it is called \(H\)-supermagic. In this paper, we investigate the existence of super \((a,d)\)-\(C_4\)-antimagic labeling of book graphs, for difference \(d=0,1\) and \(n\geq2\).

Keywords: Book graph, super \((a,d)\)-\(C_4\)-antimagic, disjoint union, super \((b,0)\)-\(C_4\)-antimagicness.

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 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 book graphs \(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:
\begin{align}\label{partial_sum2} \nonumber wt_\alpha(C_4^{(j)}) &= \sum\limits_{v\in V(C_4^{(j)})} \alpha(v) + \sum\limits_{e\in E(C_4^{(j)})} \alpha(e).\\ &=\sum_{k=1}^{2}\alpha(y_k)+ \alpha(y_1y_2)+\sum_{k=1}^{2} \alpha(x_{(k,j)})+ \sum_{k=1}^{2} \alpha(y_kx_{(k,j)})+\alpha(x_{(1,j)}x_{(2,j)}) \end{align}
(1)

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

\begin{equation}\label{semi_final1} \alpha (y_1)+\alpha (y_2) +\alpha(y_1y_2)= 2(n+3). \end{equation}
(2)
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

\begin{equation}\label{semi_final2} \psi(y_1)+\psi (y_2) +\psi(y_1y_2)= 2(n+3). \end{equation}
(3)
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.

References:

  1. Gutiérrez, A., & Lladó, A. (2005). Magic coverings. J. Combin. Math. Combin. Comput. 55, 43-56. [Google Scholor]
  2. Lladó, A., & Moragas, J. (2007). Cycle-magic graphs. Discrete Mathematics, 307(23), 2925-2933. [Google Scholor]
  3. Ngurah, A. A. G., Salman, A. N. M., & Susilowati, L. (2010). H-supermagic labelings of graphs. Discrete Mathematics, 310(8), 1293-1300. [Google Scholor]
  4. Maryati, T. K., Baskoro, E. T., & Salman, A. N. M. (2008). P~ h-supermagic labelings of some trees. Journal of Combinatorial Mathematics and Combinatorial Computing, 65, 198–204. [Google Scholor]
  5. Jeyanthi, P., & Selvagopal, P. (2010). More classes of H-supermagic graphs. Intern. J. of Algorithms, Computing and Mathematics, 3(1), 93-108.[Google Scholor]
  6. Maryati, T. K., Salman, A. N. M., & Baskoro, E. T. (2013). Supermagic coverings of the disjoint union of graphs and amalgamations. Discrete Mathematics, 313(4), 397-405. [Google Scholor]
  7. Inayah, N., Salman, A. N. M., & Simanjuntak, R. (2009). On (a, d)-H-antimagic coverings of graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 71, 273–281. [Google Scholor]
  8. Inayah, N., Simanjuntak, R., Salman, A. N. M.,& Syuhada, K. I. A. (2013). Super (a, d)-H-antimagic total labelings for shackles of a connected graph H. Australasian Journal Of Combinatorics, 57, 127-138.[Google Scholor]
  9. Baca, M., Lin, Y. Q., Muntaner Batle, F. A., & Rius Font, M. (2009). Strong labelings of linear forests. Acta mathematica sinica. English series, 25(12), 1951-1964. [Google Scholor]
  10. Baca, M., & Miller, M. (2008). Super edge-antimagic graphs: A wealth of problems and some solutions. Universal-Publishers.[Google Scholor]
  11. Figueroa-Centeno, R. M., Ichishima, R., & Muntaner-Batle, F. A. (2001). The place of super edge-magic labelings among other classes of labelings. Discrete Mathematics, 231(1-3), 153-168. [Google Scholor]
  12. Marr, A. M., & Wallis, W. D. (2012). Magic graphs. Springer Science & Business Media.[Google Scholor]
  13. Lih, K. W. (1983). On magic and consecutive labelings of plane graphs. Utilitas Math, 24, 165-197.[Google Scholor]
  14. Baca, M., Brankovic, L., & Semanicová-Fenovcíková, A. (2011). Labelings of plane graphs containing Hamilton path. Acta Mathematica Sinica, English Series, 274), 701-714. [Google Scholor]
  15. Baca, M., Miller, M., Phanalasy, O., & Semanicová-Fenovcíková, A. (2010). Super d-antimagic labelings of disconnected plane graphs. Acta Mathematica Sinica, English Series, 26(12), 2283-2294. [Google Scholor]
  16. Baca, M., Numan, M., & Shabbir, A. (2013). Labelings of type (1, 1, 1) for toroidal fullerenes. Turkish Journal of Mathematics, 37(6), 899-907.[Google Scholor]