A graph \(G=(V,E)\) is \(H\)-supermagic if there exists a bijection \(f\) from the set \(V\cup E\) to the set of integers \(\{1,2,3,\dots,|V|+|E|\}\), called \(H\)-supermagic labeling such that the sum of labels of all elements of every induced subgraph of \(G\) isomorphic to \(H\) is equal to the same integer and all vertex labels are in \(\{1,2,3,\dots,|V|\}\). We present a \((K_4-e)\)-supermagic labeling of the triangular ladder \(TL_{2n}\) for any \(n\geq2\).
Let \(G\) and \(H\) be graphs. Then \(G\) is said to have an \(H\)-covering if there exists a set \(\mathcal{H}=\{H_1,H_2,\dots,H_s\}\) of subgraphs of \(G\), all isomorphic to \(H\), such that every edge of \(G\) is contained in at least one graph in \(\mathcal{H}\). Also \(G\) is said to have an \(H\)-decomposition if every edge of \(G\) is contained in exactly one graph in \(\mathcal{H}\). Therefore, every \(H\)-decomposition is also an \(H\) covering, but the converse is not always true. The set \(\mathcal{H}\) is called a maximal \(H\)-covering if it contains all subgraphs of \(G\) isomorphic to \(H\).
Suppose \(G(V,E)\) is a graph with an \(H\)-covering. Then a function \(f\) from \(V\cup E\) to the set of integers \(\{1,2,\dots, |V|+|E|\}\) is called an \(H\)-magic labeling of \(G\) if there exists a positive integer \(\mu\) such that for every subgraph \(H_i\) of \(G\) with the vertex set \(V_i\) and edge set \(E_i\) the sum \(w(H_i)\) (called the weight of \(H_i\)) satisfies \[w(H_i) = \sum_{x\in V_i} f(x) + \sum_{e\in E_i} f(e) = \mu.\]
The graph \(G\) is then called an \(H\)-magic graph. If \(f(V)\), the set of labels of all vertices of \(V\), is moreover equal to \(\{1,2,\dots,|V|\}\), then \(f\) is called an \(H\)-supermagic labeling of \(G\) (or \(H\)-SML for short) and \(G\) is an \(H\)-supermagic graph.
Similarly, when \(\mathcal{H}\) is an \(H\)-decomposition of \(G\) and the function \(f\) described above exists (that is, \(f\) is and \(H\)-SML), then \(\mathcal{H}\) is called an \(H\)-magic or \(H\)-supermagic decomposition of \(G\).
The notions of \(H\)-magic and \(H\)-supermagic labelings were introduced by Gutiérrez and Lladó [3] in 2005. While some \(H\)-magic decompositions appeared in various papers when the unique \(H\)-cover of some graph \(G\) was in fact a decomposition, the notion itself was first time formalized by Inayah, Lladó, and Moragas [4] in 2012.
Probably the most popular graph \(H\) for which the \(H\)-magic and \(H\)-supermagic property has been studied is \(C_m\), and among those \(C_4\) is the leader, closely followed by \(C_3\). There are dozens of papers dealing with \(C_m\)-magic and supermagic labelings. We are not going to list them here, instead we refer the reader to section 5.4 in an excellent survey by Gallian [2].
We present an \(H\)-supermagic labeling of the triangular ladder \(TL_{2n}\) for \(H=K_4-e\). Triangular ladders were studies with respect to a \(C_3\)-supermagic labeling by Khalid, Rizvi, and Ali [5] and by Rizvi, Ali, and Hussain [6].
Disclaimer. The text of the Introduction is taken almost verbatim from author’s paper [1].
A triangular ladder \(TL_{2n}\) of order \(2n\) is a graph consisting of two paths \(P_n\) (called rails) on vertices \(x_1,x_2,\dots,x_{n}\) (upper rail) and \(y_1,y_2,\dots,y_{n}\) (lower rail) with edges \(a_i=x_ix_{i+1}\) and \(b_i=y_iy_{i+1}\), \(i\in[1,n-1]\), respectively, and a set of edges (called rungs) forming two perfect matchings with edges \(d_i=x_iy_i\) for \(i=1,2,\dots,n\) (called vertical rungs) and \(t_i=y_ix_{i+1}\) for \(i=1,2,\dots,n-1\) (called tilt rungs).
To illustrate the labeling for readers convenience in our proofs, we place the labels in an array as follows. One can observe that the labels correspond to the placement of the labeled elements in Figure 1.
\[\begin{array}{ccccccc} \dots&f(x_{i-1}) &f(a_{i-1}) &f(x_i) &f(a_i) &f(x_{i+1}) &\dots\\ \dots&f(d_{i-1}) &f(t_{i-1}) &f(d_i) &f(t_i) &f(d_{i+1}) &\dots\\ \dots&f(y_{i-1}) &f(b_{i-1}) &f(y_i) &f(b_i) &f(y_{i+1}) &\dots\\ \end{array}\]
We denote by \(H^d_i\) the graph induced on vertices \(x_i,x_{i+1},y_i,y_{i+1}\) and \(H^t_i\) the graph induced on vertices \(x_i,x_{i+1},y_{i-1},y_{i}\). They are shown in Figures 2 and 3, respectively.
Construction 2.1. We label the vertices as \[f(x_i) = i, \ f(y_i) = i+n,\] and the rails as \[f(a_i) = 3n+i-1 ,\qquad\text{and}\qquad f(b_i) = 2n+i.\] Then the spokes are labeled as \[f(d_i) = 6n-2i-1, \qquad\text{and}\qquad f(t_i) = 6n-2i-2.\]
Lemma 2.2. For every \(i\in[1,n]\), the weight of \(H^d_i\) is \(w(H^d_i)=25n-5\).
Proof. We denote by \(V(H^d_i)\) and \(E(H^d_i)\) the vertex and edge set of the graph \(H^d_i\), respectively. Then \[w(H^d_i) = w(V(H^d_i)) + w(E(H^d_i)),\] where \[\begin{aligned} w(V(H^d_i)) &=f(x_i)+f(x_{i+1})+f(y_i)+f(y_{i+1})\\ &=i+(i+1)+(n+i)+(n+i+1)\\ &=2n+4i+2, \end{aligned}\] and \[\begin{aligned} w(H^d_i)&=d_i +d_{i+1} +a_i +t_i +b_i\\ &=(6n-2i-1) +(6n-2i-3)+(3n+i-1) +(6n-2i-2)+(2n+i)\\ &=23n – 4i – 7. \end{aligned}\]
Therefore, \[\begin{aligned} w(H^d_i) &=w(V(H^d_i)) + w(E(H^d_i))\\ &=(2n+4i+2) + (23n – 4i – 7)\\ &=25n-5. \end{aligned}\]
To visualize our calculations, in Figure 2, we highlight the induced graph \(H^d_i\) in blue.
The corresponding labels are also in blue, with the sum of labels in the respective columns placed below. \[\begin{array}{ccccccc} \dots&{i-1} &3n+i-2 &{i} &{3n+i-1} &{i+1} &\dots\\ \dots&6n-2i+1&6n-2i &{6n-2i-1} &{6n-2i-2} &{6n-2i-3}&\dots\\ \dots&n+{i-1}&2n+i-1 &{n+i} &{2n+i} &{n+{i+1}}&\dots\\ \hline \dots& & &{7n-1} &{11n-3} &{7n-1} &\dots\\ \end{array}\] Then for \(i\in[1,n-1]\) it is easy to observe that \[w(H^d_i) = (11n-2) + 2(7n-1) = 25n-5,\] as desired. ◻
Lemma 2.3. For every \(i\in[2,n-1]\), the weight of \(H^t_i\) is \(w(H^t_i)=25n+4\).
Proof. We have again \[w(H^d_i) = w(V(H^d_i)) + w(E(H^d_i)),\] where \[\begin{aligned} w(V(H^d_i)) &=f(x_i)+f(x_{i+1})+f(y_{i-1})+f(y_{i})\\ &=i+(i+1)+(n+i-1)+(n+i)\\ &=2n+4i, \end{aligned}\] and \[\begin{aligned} {9} w(H^d_i)&=t_{i-1} +t_{i} +a_i +d_i +b_{i-1}\\ &=(6n-2i) +(6n-2i-2)+(3n+i-1) +(6n-2i-1)+(2n+i-1)\\ &=23n – 4i – 5. \end{aligned}\]
Therefore, \[\begin{aligned} {9} w(H^d_i) &=w(V(H^d_i)) + w(E(H^d_i))\\ &=(2n+4i) + (23n – 4i – 5)\\ &=25n-5. \end{aligned}\]
In Figure 3, we highlight the induced graph \(H^t_i\) in red.
We again present the array for \(i\in[1,n-1]\) with the corresponding labels in red \[\begin{array}{ccccccc} \dots&{i-1} &3n+i-2 &{i} &{3n+i-1} &{i+1} &\dots\\ \dots&6n-2i+1 &{6n-2i} &{6n-2i-1} &{6n-2i-2} &{6n-2i-3}&\dots\\ \dots &{n+{i-1}} &{2n+i-1} &{n+i} &2n+i &n+{i+1}&\dots\\ \hline \dots &{n+{i-1}} &{8n-i-1} &{7n-1} &{9n-i-3} &{i+1} &\dots\\ \end{array}\] and observe that \[w(H^t_i)=(n+i-1)+(8n-i-1)+(7n-1)+(9n-i-3)+(i+1)=25n-5,\] which completes the proof. ◻
Our main result now follows immediately.
Theorem 2.4. Let \(H=K_4-e\). Then the triangular ladder \(TL_{2n}\) is \(H\)-supermagic for every \(n\geq2\) with the magic constant \(25n+4\).
Proof. The proof follows directly from Lemmas 2.2 and 2.3. ◻