Let \(G=(V,E,F)\) be a planar graph with vertex set \(V\), edge set \(E\), and set of faces \(F.\) For nonnegative integers \(a,b,\) and \(c\), a type \((a,b,c)\) face-magic labeling of \(G\) is an assignment of \(a\) labels to each vertex, \(b\) labels to each edge, and \(c\) labels to each face from the set of integer labels \(\{1,2,\dots a|V|+b|E|+c|F|\}\) such that each label is used exactly once, and for each \(s\)-sided face \(f \in F,\) the sum of the label of \(f\) with the labels of the vertices and edges incident with \(f\) is equal to some fixed constant \(\mu_s\) for every \(s.\) We find necessary and sufficient conditions for every quadruple \((a,b,c,n)\) such that the \(n\)-prism graph \(Y_n \cong K_2 \square C_n\) admits a face-magic labeling of type \((a,b,c)\).
Let \(a,b,\) and \(c\) be three nonnegative integers and \(G=(V,E)\) be a graph with some embedding that induces a set of faces \(F\). A labeling of type \((a,b,c)\) is an assignment of labels from the set \(\{1,2, \dots , a|V|+b|E|+c|F|\}\) such that every vertex, edge, and face receives exactly \(a,b,\) and \(c\) labels, respectively. Typically \(a,b,c \in \{0,1\},\) but at least one author has considered other integer values [6]. The weight of a face \(f\), \(w(f),\) under such a labeling is the sum of the labels incident with \(f\) along with the label of \(f.\) If the weight of every \(s\)-sided face is equal to some fixed constant (we call it a magic constant) \(\mu_s\) for all \(s,\) then we say the labeling is face-magic of type \((a,b,c)\). The figures in this article outside of Figure 1 show various examples of face-magic labelings of type \((a,b,c).\)
For any \(n\geq 3,\) the n-prism, \(Y_n \cong P_2 \square C_n\), is a graph with vertex set \(V=\{u_i,v_i: i=1,2,\dots,n\}\) and edge set \(E=\{u_iv_i,u_iu_{i+1},v_iv_{i+1}:i=1,2,\dots,n\}\). When embedded in the Euclidean plane in the natural way (see Figure 1), these vertices and edges induce a set of faces \(F=\{F_i:i=1,2,\dots,n\} \cup F_0 \cup F_{n+1},\) where each face \(F_i\) is bounded by the \(4\) edges \(\{u_iu_{i+1},v_iv_{i+1},u_iv_i,v_{i+1}v_{i+1}\}\) for \(i=1,2,\dots,n,\) while \(F_0\) and \(F_{n+1}\) are both \(n\)-sided faces bounded by the edges \(\{u_iu_{i+1}:i=1,2,\dots,n\}\) and \(\{v_iv_{i+1}:i=1,2,\dots,n\},\) respectively. Observe \(|V|=2n, |E|=3n,\) and \(|F|=n+2.\)
In the following sections we find necessary and sufficient conditions for \((a,b,c,n)\) such that \(Y_n\) admits a face-magic labeling of type \((a,b,c).\)
Some of our constructions make use of labelings related to type \((a,b,c)\) labelings. One such labeling is defined as follows. Let \(G=(V,E)\) be a graph and \(f:V \cup E \rightarrow \{1,2,\dots,|V|+|E|\}\) a bijection. If there exists a constant \(k\) such that \(f(x)+f(xy)+f(y)=k\) for every \(xy \in E,\) then \(f\) is called an edge-magic total (EMT) labeling and \(G\) is called an EMT graph. The sum \(w(xy)=f(x)+f(xy)+f(y)\) is called the weight of the edge \(xy.\)
Theorem 2.1 (Kotzig & Rosa [5]). The cycle \(C_n\) is an edge-magic total graph for all \(n\geq 3.\)
Recently, Freyberg generalized EMT labelings to allow the assignment of any number of labels to the vertices or edges [2]. Specifically, for any \(\alpha,\beta \geq 0,\) an edge-magic total labeling of type \((\alpha,\beta)\) is an assignment of labels from the set \(\{1,2,\dots,\alpha |V|+ \beta |E|\}\) such that every vertex receives exactly \(\alpha\) labels, every edge receives exactly \(\beta\) labels, and the weight of every edge is equal to some fixed constant.
Theorem 2.2 (Freyberg [2]). The cycle \(C_n\) is an edge-magic total graph of type \((\alpha,\beta)\) for \(n\geq 3\) and \(\alpha, \beta \geq 1\).
An \(m \times n\) magic rectangle is an \(m \times n\) array of the first \(mn\) positive integers such that no integer is repeated and the sum of integers in each row, column, respectively is equal to a fixed constant \(\rho, \sigma\), respectively. Magic rectangles provide a natural generalization of the more widely known magic squares. Harmuth proved the following in [3] and [4].
Theorem 2.3 (Harmuth [3,4]) An \(m\times n\) magic rectangle exists if and only if \(m \equiv n \pmod2\), except if \(m = 1\), \(n=1\), or \(m=n=2.\)
In this section, we will prove the following theorem.
Theorem 3.1. Let \(a,b,c\in \{0,1\},\) \(n\ge 3.\) The prism graph \(Y_n\) admits a face-magic labeling of type \((a,b,c)\) if and only if \((a,b,c,n)\) is not
(i) \((0,0,1,n)\) for any \(n\),
(ii) \((1,0,0,n)\) for odd \(n\),
(iii) \((1,0,1,n)\) for \(n \equiv 0 \pmod 4\).
We briefly note that for any prism \(Y_n\) with \(n\ge 3,\) the trivial type \((0,0,0)\) labeling which assigns no labels is face-magic, as each region has a weight of \(0\). In addition, it is easy to see that a type \((0,0,1)\) face magic labeling of \(Y_n\) cannot exist for any \(n\), as no two faces have the same weight. We will now examine the remaining six cases in further detail.
In the first known paper on face-magic labelings of type \((a,b,c),\) Lih found type \((1,1,0)\) face-magic labelings of some families of plane graphs including friendship graphs, wheels, some platonic solids, and prisms [6]. Of interest here is the following result.
Theorem 3.2 (Lih [6]). If \(n\ge 3\), then the prism graph \(Y_n\) admits a type \((1,1,0)\) face-magic labeling.
Since type \((1,1,0)\) face-magic labelings of prisms were completely determined in [6], we will not consider them further here. However, we will note that in the proof of Theorem 3.2, Lih found several simpler face-magic labelings of type \((a,b,c)\). Lih also used consecutive labelings, where for each \(s\) the weights of \(s\)-sided faces form a consecutive set of integers. These are also referred to as \(1\)-antimagic labelings of type \((a,b,c)\). These labelings will be referenced as relevant in the following sections.
The following two results were proven in [6]:
Theorem 3.3 (Lih [6]). If \(n\) is even, then the prism graph \(Y_n\) admits a type \((1,0,0)\) face-magic labeling.
Theorem 3.4 (Lih [6]). If \(n\) is odd, then the prism graph \(Y_n\) admits a type \((1,0,0)\) \(1\)-antimagic labeling.
As a result, the question of finding a \((1,0,0)\) face-magic labeling for odd prisms was not explored in [6]. We show that it is in fact impossible to form such a labeling, proving this for the more general case \((a,0,0)\) where \(a\) is odd.
Theorem 3.5. Let \(a,n\) be nonnegative odd integers with \(n\ge 3.\) Then the prism \(Y_n\) does not admit a type \((a,0,0)\) face-magic labeling.
Proof. Suppose that \(Y_n\) had a face-magic labeling of type \((a,0,0)\). Note that each vertex appears on the boundary of exactly one \(n\)-sided face. Let the weight of each \(n\)-sided face be \(w_n\). It follows that the sum of the vertex labels is equal to \(2w_n,\) and therefore even. However, the \(2n\) vertices of \(Y_n\) are assigned labels containing all integers from \(1\) to \(2an\), and thus the sum of the vertex labels is \(\sum_{i=1}^{2an}i=an(2an+1).\) This sum is clearly odd, contradicting the fact that the vertex labels sum to \(2w_n.\) ◻
The proof of Theorem 3.2 also made use of several labelings of type \((0,1,0)\). In particular, Lih found the following:
Theorem 3.6 (Lih [6]). If \(n\) is even, then the prism graph \(Y_n\) admits a type \((0,1,0)\) face-magic labeling.
Theorem 3.7 (Lih [6]). If \(n\) is odd then the prism graph \(Y_n\) admits a type \((0,1,0)\) \(1\)-antimagic labeling.
As in the case of \((1,0,0)\) labelings, face-magic labelings of type \((0,1,0)\) were not explored in [6] for odd \(n\). However, in contrast we will see that such labelings do in fact exist. To begin, we will prove a lemma about summing select terms in arithmetic sequences.
Lemma 3.8. Let \(k \ge 2\), \(k\ne 4,\) let \(A =\{2k+3, 2k+6, …, 5k\}\), and let \(B=\{3k+2, 3k+5,…, 6k+2\}\). Then there are subsets \(X\subset A\), \(Y \subset B\) such that \(\sum_{x\in X}x + \sum_{y \in Y} y = (2k+1)^2.\)
Proof. Let \(s(j)=\sum_{i=0}^{k-j}(6k+2-3i)-(2k+1)^2\). This is the sum of all but the \(j\) lowest elements of \(B\) minus \((2k+1)^2\) and is equal to \(\frac{(48k^2+72k+25)-(6j+6k+1)^2}{24}\) for integers \(j,k\) with \(j \le k.\) Clearly when \(j\) is positive, \(s(j)\) is decreasing. It follows that \(s(j)\) is nonnegative for \((6j+6k+1)^2\le 48k^2+72k+25\), or \(j\le \frac{\sqrt{48k^2+72k+25}-6k-1}{6}\). We will let \(j_k=\lfloor \frac{\sqrt{48k^2+72k+25}-6k-1}{6}\rfloor\), and thus \(j_k\) is the largest integer for which \(s(j)\) is nonnegative for a given value of \(k\). We have the following inequalities: \[\begin{split} & \frac{\sqrt{48k^2+72k+25}-6k-7}{6}\le j_k \le \frac{k}{6}+1, \\ &k+1-j_k \ge \frac{5k}{6}, \\ &s(j_k)\le s\left(\frac{\sqrt{48k^2+72k+25}-6k-7}{6}\right)=\frac{\sqrt{48k^2+72k+25}-3}{2}\le 4k \text{ (for $k\ge 2$)}, \\ &s(j_k-2)\le s\left(\frac{\sqrt{48k^2+72k+25}-6k-19}{6}\right)=\frac{3\sqrt{48k^2+72k+25}-27}{2}\le \frac{21k}{2}. \end{split}\]
With these initial findings, we now proceed by cases on the equivalence class of \(k\) modulo \(3\). Our general approach will be to select all but the \(j_k\) smallest values in \(B\); the sum of these elements exceeds \((2k+1)^2\) by \(s(j_k)\). We will then reduce this sum by \(s(j_k)\) by first exchanging selected values in \(B\) with smaller, unselected values until the new sum is either \((2k+1)^2 , (2k+1)^2+1,\) or \((2k+1)^2+2\). Then, we perform some exchanges between selected elements in \(B\) and elements in \(A\) until the sum is exactly \((2k+1)^2\). In the case where \(k\equiv 1 \pmod 3\), a slightly different approach will be used.
We will need to restrict to the case where \(j_k \ge 2\), which requires that \(k\ge 9.\) We can show the remaining cases here: \[\begin{split} k&=2: X=\emptyset, Y=\{11, 14\}, \\ k&=3: X=\{12\}, Y=\{17, 20\}, \\ k&=5: X=\emptyset, Y=\{17, 20, 23, 29, 32\}, \\ k&=6: X=\{18\}, Y=\{23, 26, 29, 35, 38\}, \\ k&=7: X=\{35\}, Y=\{32, 35, 38, 41, 44\}, \\ k&=8: X=\{34\}, Y=\{35, 38, 41, 44, 47, 50\}. \end{split}\]
Now, let \(a_i, b_i\) be the \(i\)th element of \(A,B\) in ascending order respectively. Note that \(|A|=k, |B|=k+1.\)
Case 1. \(k \equiv 0\pmod3\)
Begin by letting \(Y_0=\{b_i | j_k+1 \le i\le k+1\}\). The sum of elements in \(Y_0\) sum to \((2k+1)^2 + s(j_k)\le (2k+1)^2 +4k.\) Note that by replacing \(b_{i}\) with \(b_{i-i'}\), the sum decreases by \(3i'\). By replacing \(b_{j_k+1}\) with \(b_{j_k+1-i'}\) for \(1\le i' \le j_k\) or \(b_{i'+1}\) with \(b_1\) for \(j_k\le i' \le k\), we can decrease the sum by any multiple of \(3\) up to \(3k\). By repeating this again except with \(b_{j_k+1}\) and \(b_{j_k+1-i'}\) for \(1\le i' \le j_k-1\) or \(b_{i'+2}\) and \(b_2\) for \(j_k-1\le i \le k-2\), we can decrease the sum by any multiple of \(3\) up to a total of \(6k-6\). Note that this requires \(|Y_0|=k+1-j_k\ge 2\), which follows for \(k\ge 3\). Since \(6k-6\ge 4k\) for \(k \ge 3,\) we form \(Y_1\) by performing at most two replacements such that the sum of elements in \(Y_1\) exceeds \((2k+1)^2\) by either \(0, 1,\) or \(2\). If this excess is \(0\), we are done by letting \(X=\emptyset, Y=Y_1\); therefore, assume the excess is either \(1\) or \(2\).
Next, note that since \(k \equiv 0 \pmod 3\), the element \(5k-1\) belongs to \(B\), with \(5k-1=b_{2k/3}\). In addition, for each element \(b\in B\) less than or equal to \(5k-1\), \(b+1, b-2 \in A\). We would like \(Y_0\) to have at least two elements less than or equal to \(5k-1\), which therefore implies \(Y_1\) also has at least two such elements. This certainly occurs when \(2k/3 \ge j_k+2,\) which is true for all \(k \ge 6.\) If the sum of elements in \(Y_1\) exceeds \((2k+1)^2\) by \(2\), remove an element \(y\le 5k-1\) from \(Y_1\) to form \(Y,\) and let \(X=\{y-2\}\). If the sum of elements in \(Y_1\) exceeds \((2k+1)^2\) by \(1\) instead, form \(Y\) by removing two elements \(y, y'\le 5k-1\) from \(Y_1\) with \(y<y'\), and let \(X=\{y-2, y'+1\}\). In both cases, the sums of elements in \(X\) and \(Y\) are exactly \((2k+1)^2\).
Case 2. \(k \equiv 2 \pmod 3\)
Form the set \(Y_1\) as in Case 1. Next, note that since \(k\equiv 2 \pmod 3,\) the element \(5k+1\) belongs to \(B\), with \(5k+1=b_{(2k+2)/3}.\) Then for each element \(b\in B\) less than or equal to \(5k+1\), \(b-1\in A.\) We would like \(Y_1\) to have at least two elements less than or equal to \(5k+1\), which is the case when \((2k+2)/3 \ge j_k+2\). This inequality holds for all \(k\ge 5.\) If the sum of of elements in \(Y_1\) exceeds \((2k+1)^2\) by \(1\) (or \(2\)), remove \(1\) (or \(2\)) elements \(y(, y')\le 5k+1\) from \(Y_1\) to form \(Y\), and let \(X=\{y-1(, y'-1)\}.\) In both cases the sums of elements in \(X\) and \(Y\) are exactly \((2k+1)^2\).
Case 3. \(k\equiv 1 \pmod3\)
In this case, elements of \(A\) and \(B\) are all equivalent to \(2\pmod 3.\) Let \(j_k'\) be the largest integer \(j\) for which \(s(j)\) is a nonnegative multiple of \(3\). Therefore, since \(s(j-1)\equiv 2 + s(j)\pmod 3\), it follows that \(j_k' \in \{j_k, j_k-1, j_k-2\}.\) Let \(X_0=\emptyset, Y_0=\{b_i | j_k'+1 \le i \le k+1\}\). Since \(k\ge 9, j_k\ge 2\), and all indices are at least \(1\). Note that the sum of elements in \(Y_0\) exceeds \((2k+1)^2\) by at most \(s(j_k-2)\le \frac{21k}{2}.\)
As in Case 1, replacing \(b_i\) with \(b_{i-i'}\) reduces the sum by \(3i'\). In addition, note that \(b_{k+1}-a_k=k+2,\) and therefore \(b_{k+1}-a_i=b_{k+1}-a_k+a_k-a_i=4k+2-3i.\) Therefore, replacing \(b_{k+1}\) with \(a_i\) reduces the sum by \(4k+2-3i\) for any \(1\le i \le k.\) Therefore, we can decrease the sum of elements in \(Y_0\) and \(X_0\) in one of three ways:
(1) Replace \(b_{j_k'+1}\) with \(b_{j_k'+1-i'}\) for \(1\le i' \le j_k'\)
(2) Replace \(b_{i'+1}\) with \(b_1\) for \(j_k'\le i' \le k\)
(3) Remove \(b_{k+1}\) from \(Y_0\) and add \(a_{i'}\) to \(X_0\) for \(1 \le i' \le k.\)
In this way, we can reduce the sum by any multiple of \(3\) up to \(4k-1.\) Since \(k+1-j_k' \ge 4\) for \(k\ge 5\), \(Y_1\) initially has at least \(4\) elements. By repeating this process up to three additional times (with natural adjustments excluding the largest element of \(B\) and the smallest element of \(A\) each time the process repeats), we can reduce the sum by any multiple of \(3\) up to \((4k-1)+(4k-7)+(4k-13)+(4k-19)=16k-40\), which is at least \(\frac{21k}{2}\) for \(k\ge 8.\) By letting \(X, Y\) be the result of performing appropriate exchanges on sets \(X_0\) and \(Y_0\) to reduce the sum by \(s(j_k')\), the sum of elements in \(X\) and \(Y\) will be exactly \((2k+1)^2.\)
Therefore in all cases we can obtain a sum of \((2k+1)^2\), completing the proof. ◻
Theorem 3.9. If \(n\) is odd, then the prism graph \(Y_n\) admits a type \((0,1,0)\) face-magic labeling.
Proof. Let \(n=2k+1\) with \(k\ge 1.\) We provide explicit labelings for \(n=3\) and \(n=9\) in Figure 2. Therefore, we may assume that \(k \ne 1, 4.\) Form an edge labeling \(\ell'\) as follows: \[\ell'(u_iu_{i+1}) = \begin{cases} 2k+1-2i, & 1 \le i \le k ,\\ 4k+2-2i & k+1 \le i \le 2k, \\ 2k+1 & i = 2k+1 , \end{cases}\] \[\ell'(v_iv_{i+1}) = \begin{cases} 5k+3+i & 1 \le i \le k ,\\ 3k+2+i & k+1 \le i \le 2k+1, \end{cases}\] \[\ell'(u_iv_{i}) = \begin{cases} 2k+2+\frac {i-1}{2} & i\text{ is odd}, \\ 3k+2+\frac{i}{2} & i \text{ is even}. \\ \end{cases}\]
One can verify that the weight of each \(4\)-sided region in \(Y_n\) under \(\ell'\) is \(12k+8\), and the weight of the outer region exceeds that of the inner region by \(2n^2 = 2(2k+1)^2\). Let \(d_i = \ell'(v_iv_{i+1})-\ell'(u_iu_{i+1})\). For a set of indices \(S=\{i_1, i_2, …, i_s\}\), exchanging the label of \(\ell'(u_iu_{i+1})\) with \(\ell'(v_iv_{i+1})\) for all \(i \in S\) has the effect of increasing the weight of the inner region by \(\sum_{i \in S} d_i\) and decreasing the weight of the outer region by the same amount, while leaving the weights of all \(4\)-sided regions the same. Therefore, we would like to find a set \(S\) such that \(\sum_{i \in S} d_i = (2k+1)^2.\) Now, note that \[\begin{cases} \{d_{k+1}, d_{k+2}, …, d_{2k}\}=\{2k+3, 2k+6,…, 5k\},\\ \{d_{2k+1}, d_1, d_2,…, d_{k}\} = \{3k+2, 3k+5, …, 6k+2\}. \end{cases} \tag{1}\]
Denote these as \(A, B\) respectively. By Lemma 3.8, there exist subsets of \(X\subset A, Y\subset B\) such that \(\sum_{x\in X}x + \sum_{y \in Y} y = (2k+1)^2.\) Let \(S\) contain the subscripts of \(d_i\) corresponding to the elements in \(X, Y\), and form \(\ell\) by exchanging the labels of \(\ell'(a_ia_{i+1})\) and \(\ell'(b_ib_{i+1})\) for all \(i\in S\) and leaving all remaining labels the same. This once again assigns a weight of \(12k+8\) to each \(4\)-sided face, but now the weights of the two \(n\)-sided faces are equal, resulting in a \((0,1,0)\) face magic labeling. ◻
When \(n\) is odd, we have a \(1\)-antimagic labeling \(\ell'\) of type \((1,0,0)\) by Theorem 3.4. One can easily see that such a labeling can be used to form a face-magic labeling \(\ell\) of type \((1,0,1)\). Therefore, we have the following:
Theorem 3.10. If \(n\) is odd, then the prism graph \(Y_n\) admits a type \((1,0, 1)\) face-magic labeling.
We will therefore focus our attention on the case where \(n\) is even. We begin with a necessary condition for a prism to have a face magic labeling of type \((1,0,1).\) Once again we will generalize, proving the result for type \((a,0,c)\) face-magic labelings where \(a\) is any nonnegative integer and \(c\) is odd.
Theorem 3.11. Let \(a,c,n\) be nonnegative integers such that \(c\) is odd and \(n\ge 3\). If the prism graph \(Y_n\) admits a type \((a,0,c)\) face-magic labeling, then \(n \not \equiv 0 \pmod 4.\)
Proof. By way of contradiction, let \(n=4k\) for some integer \(k\), and let \(Y_n\) have an \((a,0,c)\) face magic labeling, with \(n\)-sided faces having weight \(\mu_n\) and \(4\)-sided faces having weight \(\mu_4.\) Let \(s_v\) be the sum of the vertex labels, \(s_r\) be the sum of the region labels, and \(s\) be the sum of all labels. By summing the weight of all faces, we obtain the equality \[\begin{split} 2\mu_n + n \mu_4 &= 3s_v+s_r \\ &= 2s_v + s \\ &= 2s_v+\frac{(2an+(n+2)c)(2an+(n+2)c+1)}{2}. \end{split}\]
Thus, since \(n\) is even, \(\frac{(2an+(n+2)c)(2an+(n+2)c+1)}{2}\) is also even. Furthermore, since \(2an+(n+2)c+1\) is odd, it follows that \(\frac{2an+(n+2)c}{2}\) must be an even integer. However, \(\frac{2an+(n+2)c}{2}=\frac{8ak+(4k+2)c}{2}=4ak+(2k+1)c\), which is odd. This is a contradiction, and therefore \(n \not \equiv 0 \pmod 4.\) ◻
Therefore, we see that if \(n\) is even and \(Y_n\) has a type \((1,0,1)\) face-magic labeling, then \(n\equiv 2 \pmod 4.\) We will now demonstrate that such labelings exist.
The proof of the next theorem was constructed using a type \((2,1)\) edge-magic total labeling of \(C_n\) given by Freyberg in [2]. Let \(n \equiv 2\pmod 4,\) \(C_n=(x_1,x_2,\dots,x_n)\) and \(f:V(C_n)\cup E(C_n) \rightarrow \{1,2,\dots,3n\}\) be such a labeling. Then we know \(f(x_i)+f(x_ix_{i+1})+f(x_{i+1})=\frac{15n}{2}+4\) for all \(i \in \{1,2,\dots,n\}\), where the arithmetic is performed modulo \(n.\) By assigning the label \(f(x_ix_{i+1})\) to the face \(F_i \in F(Y_n)\) and arbitrarily assigning the two labels in \(f(x_i)\) to the vertices \(u_i\) and \(v_i\) in \(V(Y_n),\) we instantly get a labeling \(\ell'\) of the vertices and \(4\)-sided faces of \(Y_n\) with the property that the weight of a \(4\)-sided face is \[\begin{array}{lll} w(F_i)&=& \ell'(u_i)+\ell'(v_i)+ \ell'(F_i)+ \ell'(u_{i+1})+ \ell'(v_{i+1})\\ &=&f(x_i)+f(x_ix_{i+1})+f(x_{i+1})\\ &=&\frac{15n}{2}+4, \end{array}\] for all \(i\in \{1,2,\dots,n\}.\) However, the two \(n\)-sided faces of \(Y_n\) need not have equal weight. We have remedied this in the proof of the next theorem by carefully partitioning \(f(x_i)\) into pairs \((\ell'(u_i), \ell'(v_i))\) such that \(\sum_{i=1}^{n}(\ell'(u_i)-\ell'(v_i))=1.\)
Theorem 3.12. If \(n\equiv 2 \pmod 4\), then the prism graph \(Y_n\) admits a type \((1,0,1)\) face-magic labeling.
Proof. Let \(n=4k+2\) for some integer \(k\geq 1.\) If \(k=1\) or \(k=2\), the corresponding labelings can be found in Figure 3. So we assume \(k\geq 3\) and we describe a labeling \(\ell: V \cup F \rightarrow \{1,2,\dots,12k+8\}\) as follows. Let \(\ell(F_0)=12k+7,\ell(F_1)=2, \ell(F_{2k+2})=12k+2,\ell(F_{n+1})=12k+8,\) and \[\ell(F_i)=\begin{cases} -8+6i & \text{for}\;i=2,3,\dots,2k+1 ,\\ 24k+18-6i & \text{for}\; i=2k+3,2k+4,\dots,4k+2. \end{cases}.\]
Now that the face labels have been assigned, we define the vertex labels in the following table.
| \(i\) | \(\ell(u_i)\) | \(\ell(v_i)\) | \(\sum_i (\ell(u_i)-\ell(v_i))\) |
| 1 | \(6k+5\) | \(12k+4\) | \(-6k+1\) |
| 2 | \(3\) | \(12k+5\) | \(-12k-2\) |
| 3 | \(12k+6\) | \(6k+1\) | \(6k+5\) |
| \(4,6,\dots,2k-4\) | \(-7+3i\) | \(12k+21-6i\) | \((k-3)(-3k-28)\) |
| \(5,7,\dots,2k+1\) | \(12k+20-6i\) | \(6k-4+3i\) | \(-3(k^2-1)\) |
| \(2k-2,2k,2k+2\) | \(12k+21-6i\) | \(-7+3i\) | \(-6(3k-14)\) |
| \(2k+3,2k+5,\dots,4k-5\) | \(18k+10-3i\) | \(-12k-10+6i\) | \((k-3)(3k+29)\) |
| \(2k+4,2k+6,\dots,4k+2\) | \(-12k-9+6i\) | \(12k+7-3i\) | \(k(3k+11)\) |
| \(4k-3,4k-1,4k+1\) | \(-12k-10+6i\) | \(18k+10-3i\) | \(-3(-6k+29)\) |
The table makes it easy enough to check that \(\ell\) is a bijection. One can also check that (amazingly!) the sum of the sums in the rightmost column in the table is \(1.\) This will be important next.
We proceed by checking the face weights. We begin with the two \(n\)-sided faces. We have \[\begin{array}{lll} w(F_0)-w(F_{n+1})&=&\ell(F_0)+\sum_{i=1}^{n}\ell(u_i) -(\ell(F_{n+1})+\sum_{i=1}^{n}\ell(v_i)) \\ & =& \ell(F_0)- \ell(F_{n+1}) + \sum_{i=1}^{n}(\ell(u_i)-\ell(v_i)) \\ &=&-1+1\\ &=&0. \end{array}\]
Therefore, \(w(F_0)=w(F_{n+1}).\) By the discussion immediately preceding this theorem, we know \(w(F_i)=\frac{15n}{2}+4\) for \(i \in \{1,2,\dots,n\}.\) Hence, \(\ell\) is a face-magic labeling of type \((1,0,1)\) and the proof is complete. ◻
Once again, when \(n\) is odd we have a \(1\)-antimagic labeling of type \((0,1,0)\) by Theorem 3.7, which easily leads to a face-magic labeling of type \((0,1,1)\). We therefore conclude the following:
Theorem 3.13. If \(n\) is odd, then the prism graph \(Y_n\) admits a type \((0, 1, 1)\) face-magic labeling.
We can use a different approach to show that this is also true when \(n\) is even.
Theorem 3.14. If \(n\) is even, then the prism graph \(Y_n\) admits a type \((0,1,1)\) face-magic labeling.
Proof. If \(n=4,\) the labeling is shown in Figure 4. Therefore we let \(n\neq 4,\) \(Y_n=(V,E,F),\) \(C_n=(x_1,x_2,\dots,x_n)\), and \(f: V(C_n) \cup E(C_n) \rightarrow \{1,2,\dots,2n\}\) an edge-magic total labeling of \(C_n.\) Then there is some integer \(k\) such that \(f(x_i)+f(x_ix_{i+1})+f(x_{i+1})=k\) for every \(i=1,2,\dots,n.\) Furthermore, in the constructions provided in [5], the element \(2n\) is always assigned as an edge label. Now we define a type \((0,1,1)\) labeling \(\ell:E\cup F \rightarrow \{1,2,\dots,4n+2\}\) as follows.
Let \(\ell(F_0)=4n+1, \ell(F_{n+1})=4n+2,\) \(\ell(u_iv_i)=f(x_i),\) and \(\ell(F_i)=f(x_ix_{i+1})\) for \(i=1,2,\dots,n.\) We have used the labels \(\{1,2,\dots,2n\}\cup \{4n+1,4n+2\}.\) Since the element \(2n\) was assigned to an edge of \(C_n\) under the edge-magic total labeling \(f\), the labeling \(\ell\) assigns the element \(2n\) to a face \(F_t\) for some \(t \in \{1,2,\dots,n\}.\)
The labeling can be completed from a \(2 \times n\) magic rectangle \(M=[m_{i,j}]\) in the following way. First, add \(2n\) to every entry in \(M.\) Necessarily, the column sums are \(\sigma=6n+1\) and the row sums are \(\rho=3n^2+n/2.\) WLOG, we may assume the first column of \(M\) is \([4n \; 2n+1]^T\). Let \(\ell(u_tu_{t+1})=4n\) and \(\ell(v_tv_{t+1})=2n+1\). Now, form an arbitrary bijection between the remaining columns of \(M\) to the pairs \((u_iu_{i+1},v_iv_{i+1})\) for \(i \in \{1,2,\dots,n\} \setminus \{t\}\) so that the first label in each pair is always taken from the first row of \(M.\) Finally, complete the construction by swapping the labels of \(F_t\) and \(v_tv_{t+1}\) so that \(\ell(F_t)=2n+1\) and \(\ell(v_tv_{t+1})=2n.\)
Clearly, \(\ell\) is a bijection, so it remains to check the weights. We begin with the two \(n\)-sided faces. We have, \[\begin{array}{lll} w(F_0) & = & \ell(F_0) + \sum_{i=1}^n \ell(u_iu_{i+1}) \\ & = & 4n+1+\sum_{j=1}^{n} m_{1,j} \\ & = & 4n+1+ \rho \\ & = & 3n^2+9n/2+1, \end{array}\] and \[\begin{array}{lll} w(F_{n+1}) & = & \ell(F_{n+1})+ \sum_{i=1}^n \ell(v_iv_{i+1}) \\ & = &4n+2 +\sum_{j=1}^{2n} m_{2,j} -1 \\ & = & 4n+1+\rho \\ & = & 3n^2+9n/2+1. \end{array}\]
Finally, let \(F_i\) be a \(4\)-sided face. Then \(i \in \{1,2,\dots,n\},\) and we have \[\begin{array}{lll} w(F_{i}) & = \ell(u_iu_{i+1})+\ell(v_iv_{i+1})+ \ell(u_iv_i) + \ell(F_i) + \ell(u_{i+1}v_{i+1})\\ &= \sigma +f(x_i)+f(x_ix_{i+1})+f(x_{i+1})\\ &= \sigma +k \\ &= 6n+1 +k. \end{array}\]
Therefore, \(\ell\) is face-magic with \(\mu_n=3n^2+9n/2+1\) and \(\mu_4=6n+1 +k.\) Since \(n\neq 4\), we have proved the claim. ◻
The generalized prism graph, \(Y^m_n \cong P_m \square C_n\) was investigated by Baca in [1]. He proved the following.
Theorem 3.15 (Bacaetal. [1]) The generalized prism graph \(Y^m_n\) admits a type \((1,1,1)\) face-magic graph whenever \(m\geq 2\) and \(n\geq 5.\)
By corollary of Theorem 3.15, we know \(Y_n\) admits a type \((1,1,1)\) face-magic graph whenever \(n\geq 5.\) Therefore, we could simply provide labelings for the cases \(n=3\) and \(n=4\) and move on. However, our construction is different from the one in [1], so we believe there is value in including it.
Theorem 3.16. If \(n\ge 3\), then the prism graph \(Y_n\) admits a type \((1,1,1)\) face-magic labeling.
Proof. If \(n=4,\) the labeling is shown in Figure 5. Let \(n\neq 4,\) \(Y_n=(V,E,F),\) \(C_n=(x_1,x_2,\dots,x_n)\), and \(f: V(C_n) \cup E(C_n) \rightarrow \{1,2,\dots,2n\}\) an edge-magic total labeling of \(C_n.\) Then there is some integer \(k\) such that \(f(x_i)+f(x_ix_{i+1})+f(x_{i+1})=k\) for every \(i=1,2,\dots,n.\) Define a type \((1,1,1)\) labeling \(\ell:V\cup E \cup F \rightarrow \{1,2,\dots,6n+2\}\) as follows.
Let \(\ell(F_0)=6n+1, \ell(F_{n+1})=6n+2,\) \(\ell(u_iv_i)=f(x_i),\) and \(\ell(F_i)=f(x_ix_{i+1})\) for \(i=1,2,\dots,n.\) We have used the labels \(\{1,2,\dots,2n\}\cup \{6n+1,6n+2\}.\) WLOG, we may assume \(\ell(F_t)=2n\) for some \(t \in \{1,2,\dots,n\}.\)
The labeling can be completed from a \(2 \times 2n\) magic rectangle \(M=[m_{i,j}]\) in the following way. First, add \(2n\) to every entry in \(M.\) Necessarily, the column sums are \(\sigma=8n+1\) and the row sums are \(\rho=n(8n+1).\) WLOG, we may assume the first column of \(M\) is \([6n \; 2n+1]^T\). Let \(\ell(u_tu_{t+1})=6n\) and \(\ell(v_tv_{t+1})=2n+1\). Now, form an arbitrary bijection between the remaining columns of \(M\) to the pairs \((u_i,v_i)\) for \(i \in\{1,2,\dots,n\}\) and \((u_iu_{i+1},v_iv_{i+1})\) for \(i \in \{1,2,\dots,n\} \setminus \{t\}\) so that the first label in each pair is always taken from the first row of \(M.\) Finally, complete the construction by swapping the labels of \(F_t\) and \(v_tv_{t+1}\) so that \(\ell(F_t)=2n+1\) and \(\ell(v_tv_{t+1})=2n.\)
Clearly, \(\ell\) is a bijection, so it remains to check the weights. We begin with the two \(n\)-sided faces. We have, \[\begin{array}{lll} w(F_0) & = & \ell(F_0) + \sum_{i=1}^n \ell(u_i) + \sum_{i=1}^n \ell(u_iu_{i+1}) \\ & = & 6n+1+\sum_{j=1}^{2n} m_{1,j} \\ & = & 6n+1+ \rho \\ & = & 8n^2+7n+1, \end{array}\] and \[\begin{array}{lll} w(F_{n+1}) & = & \ell(F_{n+1})+ \sum_{i=1}^n \ell(v_i) + \sum_{i=1}^n \ell(v_iv_{i+1}) \\ & = &6n+2 +\sum_{j=1}^{2n} m_{2,j} -1 \\ & = & 6n+1+\rho \\ & = & 8n^2+7n+1. \end{array}\]
Finally, let \(F_i\) be a \(4\)-sided face. Then \(i \in \{1,2,\dots,n\},\) and we have \[\begin{array}{lll} w(F_{i}) & = & \ell (u_i)+\ell(v_i) + \ell (u_{i+1})+\ell(v_{i+1})+\ell(u_iu_{i+1})+\ell(v_iv_{i+1})+ \ell(u_iv_i) + \ell(F_i) + \ell(u_{i+1}v_{i+1})\\ &=& 3\sigma +f(x_i)+f(x_ix_{i+1})+f(x_{i+1})\\ &=& 3 \sigma +k \\ &=& 3(8n+1) +k. \end{array}\]
Therefore, \(\ell\) is face-magic with \(\mu_n=8n^2+7n+1\) and \(\mu_4=3(8n+1)+k.\) Since \(n\neq 4\), we have proved the claim. ◻
Now we turn our attention to the case where \(a,b,c\) can be any nonnegative integers. In [6], Lih describes two ways that one can use one or more face-magic labelings to produce a new face-magic labeling of a different type.
Lemma 4.1(Lih [6]). Let \(G\) admit face-magic labelings of types \((a,b,c)\) and \((a', b', c').\) Then \(G\) also admits a face-magic labeling of type \((a+a', b+b', c+c').\)
Lemma 4.2 (Lih [6]). Let \(a,b,c, k, k', k''\) be nonnegative integers. If \(G\) admits a type \((a, b, c)\) face-magic labeling, then \(G\) also admits a type \((a+2k, b+2k', c+2k'')\) face magic labeling.
Using these two Lemmas in conjunction with Theorem 3.1, one can obtain quite a variety of face-magic labelings. We will in fact obtain a complete characterization of face-magic labelings of type \((a,b,c)\) for nonnegative \(a,b,c\). To do so, we will need to obtain a handful of new labelings.
To begin, Lemma 4.1 can be used to form a variety of different face-magic labelings. We will restrict our attention to those which are useful in proving our characterization result.
Lemma 4.3. The prism graph \(Y_n\) admits face-magic labelings of type \((0,2,1)\) for all \(n\), type \((1,2,0)\) for all \(n\), type \((1,2,1)\) for all \(n\), and type \((2,0,1)\) for \(n\equiv 2 \pmod 4\).
Proof. The type \((0,2,1), (1,2,0),\) and \((1,2,1)\) face-magic labelings can be found by combining face-magic labelings of types \((0,1,0), (1,1,0),\) and \((0,1,1),\) each of which exist for all \(n\ge 3.\) The type \((2,0,1)\) face-magic labeling for \(n \equiv 2 \pmod 4\) follows from combining face-magic labelings of types \((1,0,1)\) and \((1,0,0).\) ◻
We will now find some labelings which do not result immediately from Theorem 3.1 and Lemmas 4.1, 4.2 but which nevertheless exist.
Lemma 4.4. If \(n\not \equiv 0 \pmod 4\), then the prism graph \(Y_n\) admits a type \((2,0,1)\) face-magic labeling.
Proof. This is true for \(n\equiv 2 \pmod 4\) by Lemma 4.3. Therefore, we restrict to odd \(n.\) The labeling corresponding to \(n=3\) can be found in Figure 6. Therefore let \(n\ge 5,\) and let \(\ell\) be given by \(\ell(F_0)=\{5n+2\}, \ell(F_{n+1})=\{1\}, \ell(F_i)=\{5n+2-i\}\) for \(1\le i \le n\), and \[\begin{split} \ell(u_i)&= \begin{cases} \left\{n+1+i, \frac{6n+3-i}{2}\right\}& 1\le i \le n-2, i \text{ is odd}, \\ \left\{n+1+i, \frac{5n+3-i}{2}\right\}& 2\le i \le n-3, i \text{ is even}, \\ \{n+1, 2n+2\} &i = n-1, \\ \left\{\frac{n-1}{2}, \frac{5n+3}{2}\right\} &i = n. \end{cases} \\ \ell(v_i)&= \begin{cases} \left\{i+1, 4n+2-i\right\}& 1\le i \le \frac{n-5}{2}, \\ \left\{i+2, 4n+1-i\right\}& \frac{n-3}{2}\le i \le n-2, \\ \{2n, 3n+2\} &i = n-1, \\ \left\{2n+1, \frac{7n+7}{2}\right\} &i = n. \end{cases} \end{split}\]
Note that the labels assigned to the vertices \(u_i\) form the set \(\{(n-1)/2, n+1, …, 2n-1, 2n+2,…,3n+1\}\), and the labels assigned to vertices \(v_i\) form the set \(\{2,…, (n-3)/2, (n+1)/2, …, n, 2n, 2n+1, 3n+2, …, 4n+1\}\). These sum to \(4n^2+\frac{n-1}{2}\) and \(4n^2+\frac{11n+1}{2}\) respectively. Therefore, we see that the two \(n\)-sided faces each have a weight of \(4n^2+\frac{11n+3}{2}\). (In the case \(n=5,\) the first line of the label for \(\ell(v_i)\) is ignored. Furthermore, note that \(2=(n-1)/2\) and \(4n+1 = \frac{7n+7}{2}.\) Therefore the labels assigned to vertices \(v_i\) are \(\{3, 4, 5, 10, 11, 17, 18, 19, 20, 21\}\), which sum to \(128=4n^2+\frac{11n+1}{2}\). Thus the same argument holds.) It can be verified that each \(4\)-sided face has a weight of \(\frac{41n+27}{2}\). Thus, \(\ell\) is a type \((2,0,1)\) face magic labeling of \(Y_n.\) ◻
Lemma 4.5. If \(n \not \equiv 0 \pmod 4,\) then the prism graph \(Y_n\) admits a type \((0,0,3)\) face-magic labeling.
Proof. The columns of a \(3\times n\) magic rectangle form a face-magic labeling of type \((0,0,3)\) for odd \(n\). Therefore, we focus on the case where \(n\equiv 2 \pmod 4.\) Let \(n=2k,\) with \(k\ge 3\) odd, and let \(f:\{1,…, n+1\}\rightarrow (\{1,…, 3n+6\})^3\) be given by \[f(i)=\begin{cases} (2i-1, 2n+4-i, 2n+6+k-i)& 1\le i \le k+1, \\ (2i-n-2, 2n+4-i, 3n+7+k-i) & k+2 \le i \le n+1 .\\ \end{cases} \tag{2}\]
Let \(f_1, f_2, f_3\) be the projections maps, let \(X_j\) be the image of \(\{1,…, n+1\}\) under \(f_j\), let \(Y_i=\{f_1(i), f_2(i), f_3(i)\}\), and let \(s_i=f_1(i)+f_2(i)+f_3(i)\). We observe that \(f_1, f_2, f_3\) are each injections, and \(X_1=\{1,…, n+1\},\) \(X_2=\{n+3,…, 2n+3\}\), and \(X_3=\{2n+5,…, 3n+5\}.\) In addition, \(s_i=9k+9\) for all \(i\). Now, note that \(2n+4< \frac{9k+9}{2}< 3n+6\) for all positive \(n\), and \(\frac{9k+9}{2}\in \mathbb{Z}\) for all odd \(k\). Therefore, \(f_3(i)=\frac{9k+9}{2}\) for some \(i\). Let \(f_3^{-1}(\frac{9k+9}{2})=i^*.\) Note that \(f_1(i^*)+f_2(i^*)=f_3(i^*)=\frac{9k+9}{2}.\)
We now form our \((0,0,3)\) labeling as follows: \[\ell(F_i)=\begin{cases} Y_i& 1\le i \le n, i \ne i^* ,\\ Y_{n+1} & i=i^* \text{ unless $i^*=n+1$} ,\\ \{n+2, 2n+4, f_3(i^*)\} &i = 0 ,\\ \{3n+6, f_1(i^*), f_2(i^*)\} &i = n+1. \end{cases} \tag{3}\]
For \(1 \le i \le n\), \(w(F_i)=9k+9.\) For \(i \in \{0, n+1\}\), \(w(F_i)=3n+6+\frac{9k+9}{2}.\) ◻
Lemma 4.6. If \(n\) is odd, then the prism graph \(Y_n\) admits a type \((1,0,2)\) face-magic labeling.
Proof. Let \(n=2k+1\). Begin by considering the function \(f:\{1,…, n+2\}\rightarrow \mathcal{P}(\{2n+1,…, 4n+4\})\) given by \[f(i)=\begin{cases} \{2n+2i-1, 4n+5-i\}& 1\le i \le k+2 ,\\ \{2i+n-3, 4n+5-i\} & k+3 \le i \le n+2 .\\ \end{cases} \tag{4}\]
One can note that the sums of elements in \(f(i)\) sum to \(6n+4+i\) for \(1\le i \le k+2\) and \(5n+2+i\) for \(k+3\le i \le n+2\). These form a set of consecutive integers from \(5n+k+5\) to \(6n+k+6\). A \((1,0,2)\) face-magic labeling of \(Y_n\) can then be formed by taking a \(1\)-antimagic labeling of type \((1,0,0)\) and assigning labels \(f(i)\) to the faces of \(Y_n\) in complementary fashion. ◻
We are now prepared to state and prove the generalization of Theorem 3.1.
Theorem 4.7. Let \(a,b,c\) be nonnegative integers, and let \(n\ge 3.\) The prism graph \(Y_n\) admits a face-magic labeling of type \((a,b,c)\) if and only if \((a,b,c,n)\) is not
(i) \((0,0,1,n)\) for any \(n\),
(ii) \((a,0,0,n)\) for odd \(a, n\),
(iii) \((a,0,c,n)\) for any \(a,\) odd \(c\), and \(n \equiv 0 \pmod 4\).
Proof. First note that the nonexistence of type \((0,0,1)\) face-magic labelings is trivial, and that the remaining nonexistence results are given in Theorems 3.5 and 3.11. To show that the rest of the labelings do exist, we proceed by cases on the parities of \(a,b,c\), as well as the equivalence class of \(n \pmod 4.\) By Theorem 3.1 and Lemma 4.2, we only need to consider the following cases:
Case 1. \(a,b,\) are even, \(c\) is odd
If \(b\ge 2,\) a face-magic labeling is given by the type \((0,2,1)\) face-magic labeling given in Lemma 4.3 and the application of Lemma 4.2. If \(b=0\) and \(n\equiv 0 \pmod 4,\) then this is the case \((a,0,c,n)\) with \(c\) odd and \(n\equiv 0 \pmod 4,\) for which no face-magic labeling exists. Otherwise if \(b=0\), \((a,b,c)\ne (0,0,1),\) and \(n \not \equiv 0 \pmod 4\), then a face-magic labeling is obtained by the type \((2, 0, 1)\) and \((0,0,3)\) face-magic labelings given in Lemmas 4.4, 4.5 and the application of Lemma 4.2.
Case 2. \(a, n\) are odd, \(b,c\) are even
If \(b=c=0\) then this is the case \((a,0,0,n)\) for odd \(a,n\) and no face-magic labeling exists. Otherwise, a face-magic labeling is given by the type \((1,2,0)\) and \((1, 0, 2)\) face-magic labelings given in Lemmas 4.3, 4.6 and the application of Lemma 4.2.
Case 3. \(a, c\) are odd, \(b\) is even, \(n \equiv 0 \pmod 4\)
If \(b=0\), then this is the case \((a,0,c,n)\) with \(c\) odd and \(n\equiv 0 \pmod 4,\) for which no face-magic labeling exists. Otherwise, a face-magic labeling is given by the type \((1,2,1)\) face-magic labeling given in Lemma 4.3 and the application of Lemma 4.2.
◻
We begin with a brief remark on the construction of type \((1,1,1)\) face-magic labelings in Theorem 3.16. When \(n\) is even, the construction in the proof of Theorem 3.16 is similar to combining a type \((0,1,1)\) face-magic labeling with a type \((1,0,0)\) face-magic labeling using Lemma 4.1. When \(n\) is odd, a type \((1,1,1)\) face-magic labeling can also be obtained by combining a type \((1,0,1)\) face-magic labeling with a type \((0,1,0)\) face-magic labeling. However, given the lack of elegance in the given \((0,1,0)\) face-magic labeling, the construction in the proof of Theorem 3.16 is here much preferred for odd \(n\). On a related note, an improved construction of the type \((0,1,0)\) labeling for odd prisms would be welcome.
There are several possible ways this research could be extended. For instance, one could attempt to provide a complete characterization of type \((a,b,c)\) face-magic labelings for other families of graphs. Two natural choices include generalized prisms and disjoint unions of prisms. One special benefit of the disjoint union of prisms is that the same label exchanging method that proved useful here would also apply to disjoint unions of prisms. However, the fact that these graphs are disconnected means that the embedding may have a significant impact on whether or not the graph admits a face-magic labeling. Therefore, we pose two open problems. Let \(mY_n\) refer to the disjoint union of \(m\) copies of \(Y_n\).
Problem 5.1. Can the ordered tuples \((a,b,c,m,n)\) for which the generalized prism \(Y_n^m\) admits a type \((a,b,c)\) face-magic labeling be completely determined?
Problem 5.2. Can the ordered tuples \((a,b,c,m,n)\) for which some embedding of the disjoint union \(mY_n\) admits a type \((a,b,c)\) face-magic labeling be completely determined?