Type (a,b,c) face-magic labelings of prism graphs

Andrew Bowling1, Bryan Freyberg2
1Department of Chemical Engineering, University of Minnesota Duluth, MN 55812 USA
2Department of Mathematics and Statistics, University of Minnesota Duluth, MN 55812 USA

Abstract

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,a|V|+b|E|+c|F|} such that each label is used exactly once, and for each s-sided face fF, the sum of the label of f with the labels of the vertices and edges incident with f is equal to some fixed constant μs for every s. We find necessary and sufficient conditions for every quadruple (a,b,c,n) such that the n-prism graph YnK2◻Cn admits a face-magic labeling of type (a,b,c).

Keywords: graph labeling, type (a,b,c) face-magic, prism graph

1. Introduction

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,,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{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) μ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 n3, the n-prism, YnP2◻Cn, is a graph with vertex set V={ui,vi:i=1,2,,n} and edge set E={uivi,uiui+1,vivi+1:i=1,2,,n}. When embedded in the Euclidean plane in the natural way (see Figure 1), these vertices and edges induce a set of faces F={Fi:i=1,2,,n}F0Fn+1, where each face Fi is bounded by the 4 edges {uiui+1,vivi+1,uivi,vi+1vi+1} for i=1,2,,n, while F0 and Fn+1 are both n-sided faces bounded by the edges {uiui+1:i=1,2,,n} and {vivi+1:i=1,2,,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 Yn admits a face-magic labeling of type (a,b,c).

2. Tools

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:VE{1,2,,|V|+|E|} a bijection. If there exists a constant k such that f(x)+f(xy)+f(y)=k for every xyE, 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 Cn is an edge-magic total graph for all n3.

Recently, Freyberg generalized EMT labelings to allow the assignment of any number of labels to the vertices or edges [2]. Specifically, for any α,β0, an edge-magic total labeling of type (α,β) is an assignment of labels from the set {1,2,,α|V|+β|E|} such that every vertex receives exactly α labels, every edge receives exactly β labels, and the weight of every edge is equal to some fixed constant.

Theorem 2.2 (Freyberg [2]). The cycle Cn is an edge-magic total graph of type (α,β) for n3 and α,β1.

An m×n magic rectangle is an m×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 ρ,σ, 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×n magic rectangle exists if and only if mn(mod2), except if m=1, n=1, or m=n=2.

3. Type (a,b,c) with a,b,c{0,1}

In this section, we will prove the following theorem.

Theorem 3.1. Let a,b,c{0,1}, n3. The prism graph Yn 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 n0(mod4).

We briefly note that for any prism Yn with n3, 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 Yn cannot exist for any n, as no two faces have the same weight. We will now examine the remaining six cases in further detail.

3.1. Type (1,1,0)

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 n3, then the prism graph Yn 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.

3.2. Type (1,0,0)

The following two results were proven in [6]:

Theorem 3.3 (Lih [6]). If n is even, then the prism graph Yn admits a type (1,0,0) face-magic labeling.

Theorem 3.4 (Lih [6]). If n is odd, then the prism graph Yn 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 n3. Then the prism Yn does not admit a type (a,0,0) face-magic labeling.

Proof. Suppose that Yn 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 wn. It follows that the sum of the vertex labels is equal to 2wn, and therefore even. However, the 2n vertices of Yn are assigned labels containing all integers from 1 to 2an, and thus the sum of the vertex labels is i=12ani=an(2an+1). This sum is clearly odd, contradicting the fact that the vertex labels sum to 2wn. ◻

3.3. Type (0,1,0)

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 Yn admits a type (0,1,0) face-magic labeling.

Theorem 3.7 (Lih [6]). If n is odd then the prism graph Yn 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 k2, k4, let A={2k+3,2k+6,,5k}, and let B={3k+2,3k+5,,6k+2}. Then there are subsets XA, YB such that xXx+yYy=(2k+1)2.

Proof. Let s(j)=i=0kj(6k+23i)(2k+1)2. This is the sum of all but the j lowest elements of B minus (2k+1)2 and is equal to (48k2+72k+25)(6j+6k+1)224 for integers j,k with jk. Clearly when j is positive, s(j) is decreasing. It follows that s(j) is nonnegative for (6j+6k+1)248k2+72k+25, or j48k2+72k+256k16. We will let jk=48k2+72k+256k16, and thus jk is the largest integer for which s(j) is nonnegative for a given value of k. We have the following inequalities: 48k2+72k+256k76jkk6+1,k+1jk5k6,s(jk)s(48k2+72k+256k76)=48k2+72k+25324k (for k2),s(jk2)s(48k2+72k+256k196)=348k2+72k+2527221k2.

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 jk smallest values in B; the sum of these elements exceeds (2k+1)2 by s(jk). We will then reduce this sum by s(jk) 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 k1(mod3), a slightly different approach will be used.

We will need to restrict to the case where jk2, which requires that k9. We can show the remaining cases here: k=2:X=,Y={11,14},k=3:X={12},Y={17,20},k=5:X=,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}.

Now, let ai,bi be the ith element of A,B in ascending order respectively. Note that |A|=k,|B|=k+1.

Case 1. k0(mod3)

Begin by letting Y0={bi|jk+1ik+1}. The sum of elements in Y0 sum to (2k+1)2+s(jk)(2k+1)2+4k. Note that by replacing bi with bii, the sum decreases by 3i. By replacing bjk+1 with bjk+1i for 1ijk or bi+1 with b1 for jkik, we can decrease the sum by any multiple of 3 up to 3k. By repeating this again except with bjk+1 and bjk+1i for 1ijk1 or bi+2 and b2 for jk1ik2, we can decrease the sum by any multiple of 3 up to a total of 6k6. Note that this requires |Y0|=k+1jk2, which follows for k3. Since 6k64k for k3, we form Y1 by performing at most two replacements such that the sum of elements in Y1 exceeds (2k+1)2 by either 0,1, or 2. If this excess is 0, we are done by letting X=,Y=Y1; therefore, assume the excess is either 1 or 2.

Next, note that since k0(mod3), the element 5k1 belongs to B, with 5k1=b2k/3. In addition, for each element bB less than or equal to 5k1, b+1,b2A. We would like Y0 to have at least two elements less than or equal to 5k1, which therefore implies Y1 also has at least two such elements. This certainly occurs when 2k/3jk+2, which is true for all k6. If the sum of elements in Y1 exceeds (2k+1)2 by 2, remove an element y5k1 from Y1 to form Y, and let X={y2}. If the sum of elements in Y1 exceeds (2k+1)2 by 1 instead, form Y by removing two elements y,y5k1 from Y1 with y<y, and let X={y2,y+1}. In both cases, the sums of elements in X and Y are exactly (2k+1)2.

Case 2. k2(mod3)

Form the set Y1 as in Case 1. Next, note that since k2(mod3), the element 5k+1 belongs to B, with 5k+1=b(2k+2)/3. Then for each element bB less than or equal to 5k+1, b1A. We would like Y1 to have at least two elements less than or equal to 5k+1, which is the case when (2k+2)/3jk+2. This inequality holds for all k5. If the sum of of elements in Y1 exceeds (2k+1)2 by 1 (or 2), remove 1 (or 2) elements y(,y)5k+1 from Y1 to form Y, and let X={y1(,y1)}. In both cases the sums of elements in X and Y are exactly (2k+1)2.

Case 3. k1(mod3)

In this case, elements of A and B are all equivalent to 2(mod3). Let jk be the largest integer j for which s(j) is a nonnegative multiple of 3. Therefore, since s(j1)2+s(j)(mod3), it follows that jk{jk,jk1,jk2}. Let X0=,Y0={bi|jk+1ik+1}. Since k9,jk2, and all indices are at least 1. Note that the sum of elements in Y0 exceeds (2k+1)2 by at most s(jk2)21k2.

As in Case 1, replacing bi with bii reduces the sum by 3i. In addition, note that bk+1ak=k+2, and therefore bk+1ai=bk+1ak+akai=4k+23i. Therefore, replacing bk+1 with ai reduces the sum by 4k+23i for any 1ik. Therefore, we can decrease the sum of elements in Y0 and X0 in one of three ways:

(1) Replace bjk+1 with bjk+1i for 1ijk

(2) Replace bi+1 with b1 for jkik

(3) Remove bk+1 from Y0 and add ai to X0 for 1ik.

In this way, we can reduce the sum by any multiple of 3 up to 4k1. Since k+1jk4 for k5, Y1 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 (4k1)+(4k7)+(4k13)+(4k19)=16k40, which is at least 21k2 for k8. By letting X,Y be the result of performing appropriate exchanges on sets X0 and Y0 to reduce the sum by s(jk), 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 Yn admits a type (0,1,0) face-magic labeling.

Proof. Let n=2k+1 with k1. We provide explicit labelings for n=3 and n=9 in Figure 2. Therefore, we may assume that k1,4. Form an edge labeling as follows: (uiui+1)={2k+12i,1ik,4k+22ik+1i2k,2k+1i=2k+1, (vivi+1)={5k+3+i1ik,3k+2+ik+1i2k+1, (uivi)={2k+2+i12i is odd,3k+2+i2i is even.

Figure 2 Type (0,1,0) face-magic labelings of Yn

One can verify that the weight of each 4-sided region in Yn under is 12k+8, and the weight of the outer region exceeds that of the inner region by 2n2=2(2k+1)2. Let di=(vivi+1)(uiui+1). For a set of indices S={i1,i2,,is}, exchanging the label of (uiui+1) with (vivi+1) for all iS has the effect of increasing the weight of the inner region by iSdi 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 iSdi=(2k+1)2. Now, note that (1){{dk+1,dk+2,,d2k}={2k+3,2k+6,,5k},{d2k+1,d1,d2,,dk}={3k+2,3k+5,,6k+2}.

Denote these as A,B respectively. By Lemma 3.8, there exist subsets of XA,YB such that xXx+yYy=(2k+1)2. Let S contain the subscripts of di corresponding to the elements in X,Y, and form by exchanging the labels of (aiai+1) and (bibi+1) for all iS 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. ◻

3.4. Type (1,0,1)

When n is odd, we have a 1-antimagic labeling 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 of type (1,0,1). Therefore, we have the following:

Theorem 3.10. If n is odd, then the prism graph Yn 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 n3. If the prism graph Yn admits a type (a,0,c) face-magic labeling, then n0(mod4).

Proof. By way of contradiction, let n=4k for some integer k, and let Yn have an (a,0,c) face magic labeling, with n-sided faces having weight μn and 4-sided faces having weight μ4. Let sv be the sum of the vertex labels, sr 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 2μn+nμ4=3sv+sr=2sv+s=2sv+(2an+(n+2)c)(2an+(n+2)c+1)2.

Thus, since n is even, (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 2an+(n+2)c2 must be an even integer. However, 2an+(n+2)c2=8ak+(4k+2)c2=4ak+(2k+1)c, which is odd. This is a contradiction, and therefore n0(mod4). ◻

Therefore, we see that if n is even and Yn has a type (1,0,1) face-magic labeling, then n2(mod4). 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 Cn given by Freyberg in [2]. Let n2(mod4), Cn=(x1,x2,,xn) and f:V(Cn)E(Cn){1,2,,3n} be such a labeling. Then we know f(xi)+f(xixi+1)+f(xi+1)=15n2+4 for all i{1,2,,n}, where the arithmetic is performed modulo n. By assigning the label f(xixi+1) to the face FiF(Yn) and arbitrarily assigning the two labels in f(xi) to the vertices ui and vi in V(Yn), we instantly get a labeling of the vertices and 4-sided faces of Yn with the property that the weight of a 4-sided face is w(Fi)=(ui)+(vi)+(Fi)+(ui+1)+(vi+1)=f(xi)+f(xixi+1)+f(xi+1)=15n2+4, for all i{1,2,,n}. However, the two n-sided faces of Yn need not have equal weight. We have remedied this in the proof of the next theorem by carefully partitioning f(xi) into pairs ((ui),(vi)) such that i=1n((ui)(vi))=1.

Theorem 3.12. If n2(mod4), then the prism graph Yn admits a type (1,0,1) face-magic labeling.

Proof. Let n=4k+2 for some integer k1. If k=1 or k=2, the corresponding labelings can be found in Figure 3. So we assume k3 and we describe a labeling :VF{1,2,,12k+8} as follows. Let (F0)=12k+7,(F1)=2,(F2k+2)=12k+2,(Fn+1)=12k+8, and (Fi)={8+6ifori=2,3,,2k+1,24k+186ifori=2k+3,2k+4,,4k+2..

Figure 3 Type (1,0,1) face-magic labelings of Yn

Now that the face labels have been assigned, we define the vertex labels in the following table.

i (ui) (vi) i((ui)(vi))
1 6k+5 12k+4 6k+1
2 3 12k+5 12k2
3 12k+6 6k+1 6k+5
4,6,,2k4 7+3i 12k+216i (k3)(3k28)
5,7,,2k+1 12k+206i 6k4+3i 3(k21)
2k2,2k,2k+2 12k+216i 7+3i 6(3k14)
2k+3,2k+5,,4k5 18k+103i 12k10+6i (k3)(3k+29)
2k+4,2k+6,,4k+2 12k9+6i 12k+73i k(3k+11)
4k3,4k1,4k+1 12k10+6i 18k+103i 3(6k+29)

The table makes it easy enough to check that 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 w(F0)w(Fn+1)=(F0)+i=1n(ui)((Fn+1)+i=1n(vi))=(F0)(Fn+1)+i=1n((ui)(vi))=1+1=0.

Therefore, w(F0)=w(Fn+1). By the discussion immediately preceding this theorem, we know w(Fi)=15n2+4 for i{1,2,,n}. Hence, is a face-magic labeling of type (1,0,1) and the proof is complete. ◻

3.5. Type (0,1,1)

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 Yn 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 Yn admits a type (0,1,1) face-magic labeling.

Proof. If n=4, the labeling is shown in Figure 4. Therefore we let n4, Yn=(V,E,F), Cn=(x1,x2,,xn), and f:V(Cn)E(Cn){1,2,,2n} an edge-magic total labeling of Cn. Then there is some integer k such that f(xi)+f(xixi+1)+f(xi+1)=k for every i=1,2,,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 :EF{1,2,,4n+2} as follows.

Let (F0)=4n+1,(Fn+1)=4n+2, (uivi)=f(xi), and (Fi)=f(xixi+1) for i=1,2,,n. We have used the labels {1,2,,2n}{4n+1,4n+2}. Since the element 2n was assigned to an edge of Cn under the edge-magic total labeling f, the labeling assigns the element 2n to a face Ft for some t{1,2,,n}.

Figure 4 A type (0,1,1) face-magic labeling of Y4

The labeling can be completed from a 2×n magic rectangle M=[mi,j] in the following way. First, add 2n to every entry in M. Necessarily, the column sums are σ=6n+1 and the row sums are ρ=3n2+n/2. WLOG, we may assume the first column of M is [4n2n+1]T. Let (utut+1)=4n and (vtvt+1)=2n+1. Now, form an arbitrary bijection between the remaining columns of M to the pairs (uiui+1,vivi+1) for i{1,2,,n}{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 Ft and vtvt+1 so that (Ft)=2n+1 and (vtvt+1)=2n.

Clearly, is a bijection, so it remains to check the weights. We begin with the two n-sided faces. We have, w(F0)=(F0)+i=1n(uiui+1)=4n+1+j=1nm1,j=4n+1+ρ=3n2+9n/2+1, and w(Fn+1)=(Fn+1)+i=1n(vivi+1)=4n+2+j=12nm2,j1=4n+1+ρ=3n2+9n/2+1.

Finally, let Fi be a 4-sided face. Then i{1,2,,n}, and we have w(Fi)=(uiui+1)+(vivi+1)+(uivi)+(Fi)+(ui+1vi+1)=σ+f(xi)+f(xixi+1)+f(xi+1)=σ+k=6n+1+k.

Therefore, is face-magic with μn=3n2+9n/2+1 and μ4=6n+1+k. Since n4, we have proved the claim. ◻

3.6. Type (1,1,1)

The generalized prism graph, YnmPm◻Cn was investigated by Baca in [1]. He proved the following.

Theorem 3.15 (Bacaetal. [1]) The generalized prism graph Ynm admits a type (1,1,1) face-magic graph whenever m2 and n5.

By corollary of Theorem 3.15, we know Yn admits a type (1,1,1) face-magic graph whenever n5. 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 n3, then the prism graph Yn admits a type (1,1,1) face-magic labeling.

Proof. If n=4, the labeling is shown in Figure 5. Let n4, Yn=(V,E,F), Cn=(x1,x2,,xn), and f:V(Cn)E(Cn){1,2,,2n} an edge-magic total labeling of Cn. Then there is some integer k such that f(xi)+f(xixi+1)+f(xi+1)=k for every i=1,2,,n. Define a type (1,1,1) labeling :VEF{1,2,,6n+2} as follows.

Let (F0)=6n+1,(Fn+1)=6n+2, (uivi)=f(xi), and (Fi)=f(xixi+1) for i=1,2,,n. We have used the labels {1,2,,2n}{6n+1,6n+2}. WLOG, we may assume (Ft)=2n for some t{1,2,,n}.

The labeling can be completed from a 2×2n magic rectangle M=[mi,j] in the following way. First, add 2n to every entry in M. Necessarily, the column sums are σ=8n+1 and the row sums are ρ=n(8n+1). WLOG, we may assume the first column of M is [6n2n+1]T. Let (utut+1)=6n and (vtvt+1)=2n+1. Now, form an arbitrary bijection between the remaining columns of M to the pairs (ui,vi) for i{1,2,,n} and (uiui+1,vivi+1) for i{1,2,,n}{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 Ft and vtvt+1 so that (Ft)=2n+1 and (vtvt+1)=2n.

Clearly, is a bijection, so it remains to check the weights. We begin with the two n-sided faces. We have, w(F0)=(F0)+i=1n(ui)+i=1n(uiui+1)=6n+1+j=12nm1,j=6n+1+ρ=8n2+7n+1, and w(Fn+1)=(Fn+1)+i=1n(vi)+i=1n(vivi+1)=6n+2+j=12nm2,j1=6n+1+ρ=8n2+7n+1.

Finally, let Fi be a 4-sided face. Then i{1,2,,n}, and we have w(Fi)=(ui)+(vi)+(ui+1)+(vi+1)+(uiui+1)+(vivi+1)+(uivi)+(Fi)+(ui+1vi+1)=3σ+f(xi)+f(xixi+1)+f(xi+1)=3σ+k=3(8n+1)+k.

Therefore, is face-magic with μn=8n2+7n+1 and μ4=3(8n+1)+k. Since n4, we have proved the claim. ◻

4. General (a,b,c)

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 Yn 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 n2(mod4).

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 n3. The type (2,0,1) face-magic labeling for n2(mod4) 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 n0(mod4), then the prism graph Yn admits a type (2,0,1) face-magic labeling.

Proof. This is true for n2(mod4) by Lemma 4.3. Therefore, we restrict to odd n. The labeling corresponding to n=3 can be found in Figure 6. Therefore let n5, and let be given by (F0)={5n+2},(Fn+1)={1},(Fi)={5n+2i} for 1in, and (ui)={{n+1+i,6n+3i2}1in2,i is odd,{n+1+i,5n+3i2}2in3,i is even,{n+1,2n+2}i=n1,{n12,5n+32}i=n.(vi)={{i+1,4n+2i}1in52,{i+2,4n+1i}n32in2,{2n,3n+2}i=n1,{2n+1,7n+72}i=n.

Note that the labels assigned to the vertices ui form the set {(n1)/2,n+1,,2n1,2n+2,,3n+1}, and the labels assigned to vertices vi form the set {2,,(n3)/2,(n+1)/2,,n,2n,2n+1,3n+2,,4n+1}. These sum to 4n2+n12 and 4n2+11n+12 respectively. Therefore, we see that the two n-sided faces each have a weight of 4n2+11n+32. (In the case n=5, the first line of the label for (vi) is ignored. Furthermore, note that 2=(n1)/2 and 4n+1=7n+72. Therefore the labels assigned to vertices vi are {3,4,5,10,11,17,18,19,20,21}, which sum to 128=4n2+11n+12. Thus the same argument holds.) It can be verified that each 4-sided face has a weight of 41n+272. Thus, is a type (2,0,1) face magic labeling of Yn. ◻

Lemma 4.5. If n0(mod4), then the prism graph Yn admits a type (0,0,3) face-magic labeling.

Proof. The columns of a 3×n magic rectangle form a face-magic labeling of type (0,0,3) for odd n. Therefore, we focus on the case where n2(mod4). Let n=2k, with k3 odd, and let f:{1,,n+1}({1,,3n+6})3 be given by (2)f(i)={(2i1,2n+4i,2n+6+ki)1ik+1,(2in2,2n+4i,3n+7+ki)k+2in+1.

Let f1,f2,f3 be the projections maps, let Xj be the image of {1,,n+1} under fj, let Yi={f1(i),f2(i),f3(i)}, and let si=f1(i)+f2(i)+f3(i). We observe that f1,f2,f3 are each injections, and X1={1,,n+1}, X2={n+3,,2n+3}, and X3={2n+5,,3n+5}. In addition, si=9k+9 for all i. Now, note that 2n+4<9k+92<3n+6 for all positive n, and 9k+92Z for all odd k. Therefore, f3(i)=9k+92 for some i. Let f31(9k+92)=i. Note that f1(i)+f2(i)=f3(i)=9k+92.

We now form our (0,0,3) labeling as follows: (3)(Fi)={Yi1in,ii,Yn+1i=i unless i=n+1,{n+2,2n+4,f3(i)}i=0,{3n+6,f1(i),f2(i)}i=n+1.

For 1in, w(Fi)=9k+9. For i{0,n+1}, w(Fi)=3n+6+9k+92. ◻

Lemma 4.6. If n is odd, then the prism graph Yn admits a type (1,0,2) face-magic labeling.

Proof. Let n=2k+1. Begin by considering the function f:{1,,n+2}P({2n+1,,4n+4}) given by (4)f(i)={{2n+2i1,4n+5i}1ik+2,{2i+n3,4n+5i}k+3in+2.

One can note that the sums of elements in f(i) sum to 6n+4+i for 1ik+2 and 5n+2+i for k+3in+2. These form a set of consecutive integers from 5n+k+5 to 6n+k+6. A (1,0,2) face-magic labeling of Yn can then be formed by taking a 1-antimagic labeling of type (1,0,0) and assigning labels f(i) to the faces of Yn 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 n3. The prism graph Yn 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 n0(mod4).

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(mod4). 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 b2, 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 n0(mod4), then this is the case (a,0,c,n) with c odd and n0(mod4), for which no face-magic labeling exists. Otherwise if b=0, (a,b,c)(0,0,1), and n0(mod4), 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, n0(mod4)

If b=0, then this is the case (a,0,c,n) with c odd and n0(mod4), 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.

 ◻

5. Concluding Remarks

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 mYn refer to the disjoint union of m copies of Yn.

Problem 5.1. Can the ordered tuples (a,b,c,m,n) for which the generalized prism Ynm 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 mYn admits a type (a,b,c) face-magic labeling be completely determined?

References:

  1. M. Bača, M. Newman, and A. Semaničová-Feňovčíková. Super d-antimagic labelings of generalized prism. Utilitas Mathematica, 99:101–119, 2016.
  2. B. Freyberg. Face-magic labelings of type (a,b,c) from edge-magic labelings of type (α,β). Bulletin of the Institute of Combinatorics and its Applications, 93:81–103, 2021. http://bica.the-ica.org/Volumes/93//Reprints/BICA2021-05-Reprint.pdf.
  3. T. Harmuth. Ueber magische quadrate und ähnliche zahlenfiguren. Archive of Mathematical Physics, 66:286–313, 1881.
  4. T. Harmuth. Ueber magische rechtecke mit ungeraden seitenzahlen. Archive of Mathematical Physics, 66:413–447, 1881.
  5. A. Kotzig and A. Rosa. Magic valuations of finite graphs. Canadian Mathematical Bulletin, 13:451–461, 1970. https://doi.org/10.4153/CMB-1970-084-1.
  6. K. Lih. On magic and consecutive labelings of plane graphs. Utilitas Mathematica, 24:165–197, 1983.