Let be a planar graph with vertex set , edge set , and set of faces For nonnegative integers and , a type face-magic labeling of is an assignment of labels to each vertex, labels to each edge, and labels to each face from the set of integer labels such that each label is used exactly once, and for each -sided face the sum of the label of with the labels of the vertices and edges incident with is equal to some fixed constant for every We find necessary and sufficient conditions for every quadruple such that the -prism graph admits a face-magic labeling of type .
Keywords: graph labeling, type face-magic, prism graph
1. Introduction
Let and be three nonnegative integers and be a graph with some embedding
that induces a set of faces . A
labeling of type
is an assignment of labels from the set such that
every vertex, edge, and face receives exactly and labels, respectively. Typically but at least one
author has considered other integer values [6]. The weight of a face , under such a labeling is the sum of
the labels incident with along
with the label of If the weight
of every -sided face is equal to
some fixed constant (we call it a magic constant) for all then we say the labeling is
face-magic of type . The figures in this article
outside of Figure 1 show various examples of face-magic
labelings of type
For any the
n-prism, , is a graph with vertex set and edge set
.
When embedded in the Euclidean plane in the natural way (see Figure 1),
these vertices and edges induce a set of faces where each face is bounded by the edges
for while and are both -sided faces bounded by the edges and
respectively. Observe and
In the following sections we find necessary and sufficient conditions
for such that admits a face-magic labeling of type
Figure 1 The -prism,
2. Tools
Some of our constructions make use of labelings related to type labelings. One such labeling is
defined as follows. Let be
a graph and a bijection. If there exists a constant
such that for every then is called an edge-magic total
(EMT) labeling and is called an
EMT graph. The sum is called the
weight of the edge
Theorem 2.1 (Kotzig & Rosa [5]). The cycle
is an edge-magic total graph
for all
Recently, Freyberg generalized EMT labelings to allow the assignment
of any number of labels to the vertices or edges [2]. Specifically, for any an edge-magic
total labeling of type is an assignment of labels
from the set 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 is an edge-magic total
graph of type for
and .
An magic
rectangle is an
array of the first 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 magic rectangle exists if and
only if , except
if , , or
3. Type with
In this section, we will prove the following theorem.
Theorem 3.1. Let The prism graph admits a face-magic labeling of type
if and only if is not
(i) for any
,
(ii) for odd
,
(iii) for
.
We briefly note that for any prism with the trivial type labeling which assigns no labels
is face-magic, as each region has a weight of . In addition, it is easy to see that a
type face magic labeling of
cannot exist for any , as no two faces have the same weight.
We will now examine the remaining six cases in further detail.
3.1. Type
In the first known paper on face-magic labelings of type Lih found type 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 , then the prism graph admits a type face-magic labeling.
Since type 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 . Lih also used
consecutive labelings, where for each the weights of -sided faces form a consecutive set of
integers. These are also referred to as -antimagic labelings of type . These labelings will be
referenced as relevant in the following sections.
Theorem 3.3 (Lih [6]). If is even, then the prism graph admits a type face-magic labeling.
Theorem 3.4 (Lih [6]). If is odd, then the prism graph admits a type -antimagic labeling.
As a result, the question of finding a 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 where is odd.
Theorem 3.5. Let be nonnegative odd integers with
Then the prism does not admit a type face-magic labeling.
Proof. Suppose that
had a face-magic labeling of type . Note that each vertex appears on
the boundary of exactly one -sided
face. Let the weight of each -sided face be . It follows that the sum of the
vertex labels is equal to and
therefore even. However, the
vertices of are assigned labels
containing all integers from to
, and thus the sum of the vertex
labels is This sum is
clearly odd, contradicting the fact that the vertex labels sum to
3.3. Type
The proof of Theorem 3.2 also made use of several labelings of
type . In particular, Lih
found the following:
Theorem 3.6 (Lih [6]). If is even, then the prism graph admits a type face-magic labeling.
Theorem 3.7 (Lih [6]). If is odd then the prism graph admits a type -antimagic labeling.
As in the case of
labelings, face-magic labelings of type were not explored in [6] for odd . 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 , let , and let . Then there are subsets , such that
Proof. Let .
This is the sum of all but the
lowest elements of minus and is equal to for
integers with Clearly when is positive, is decreasing. It follows that is nonnegative for , or .
We will let , and thus is the largest integer for which
is nonnegative for a given
value of . We have the following
inequalities:
With these initial findings, we now proceed by cases on the
equivalence class of modulo . Our general approach will be to select
all but the smallest values in
; the sum of these elements
exceeds by . We will then reduce this sum by
by first exchanging selected
values in with smaller,
unselected values until the new sum is either or . Then, we perform some
exchanges between selected elements in and elements in until the sum is exactly . In the case where , a slightly different
approach will be used.
We will need to restrict to the case where , which requires that We can show the remaining cases
here:
Now, let be the th element of in ascending order respectively. Note
that
Case 1.
Begin by letting . The sum of elements in sum to Note
that by replacing with , the sum decreases by . By replacing with for or with for , we can decrease the
sum by any multiple of up to
. By repeating this again except
with and for or and for , we can decrease the
sum by any multiple of up to a
total of . Note that this
requires , which
follows for . Since for we form by performing at most two
replacements such that the sum of elements in exceeds by either or . If this excess is , we are done by letting ; therefore, assume the
excess is either or .
Next, note that since , the element
belongs to , with . In addition, for each
element less than or equal
to , . We would like to have at least two elements less
than or equal to , which
therefore implies also has at
least two such elements. This certainly occurs when which is true for all
If the sum of elements in
exceeds by , remove an element from to form and let . If the sum of elements in
exceeds by instead, form by removing two elements from with , and let . In both cases, the
sums of elements in and are exactly .
Case 2.
Form the set as in Case 1.
Next, note that since the element
belongs to , with Then for each element
less than or equal to , We would like to
have at least two elements less than or equal to , which is the case when . This inequality holds
for all If the sum of of
elements in exceeds by (or ), remove (or ) elements from to form , and let In both cases the
sums of elements in and are exactly .
Case 3.
In this case, elements of and
are all equivalent to Let be the largest integer for which is a nonnegative multiple of . Therefore, since , it follows
that Let . Since , and all indices are at
least . Note that the sum of
elements in exceeds by at most
As in Case 1, replacing with
reduces the sum by
. In addition, note that
and therefore
Therefore, replacing with
reduces the sum by for any Therefore, we can decrease
the sum of elements in and
in one of three ways:
(1) Replace with
for
(2) Replace with
for
(3) Remove from and add to for
In this way, we can reduce the sum by any multiple of up to Since for , initially has at least elements. By repeating this process up
to three additional times (with natural adjustments excluding the
largest element of and the
smallest element of each time the
process repeats), we can reduce the sum by any multiple of up to ,
which is at least for
By letting be the result of performing
appropriate exchanges on sets
and to reduce the sum by , the sum of elements in and will be exactly
Therefore in all cases we can obtain a sum of , completing the proof.
Theorem 3.9. If is odd, then the prism graph admits a type face-magic labeling.
Proof. Let with
We provide explicit
labelings for and in Figure 2. Therefore,
we may assume that Form
an edge labeling as
follows:
Figure 2 Type face-magic labelings of
One can verify that the weight of each -sided region in under is , and the weight of the outer region
exceeds that of the inner region by . Let . For a set of
indices ,
exchanging the label of with for all has the effect of increasing the
weight of the inner region by and decreasing the weight of the outer region by the same
amount, while leaving the weights of all -sided regions the same. Therefore, we
would like to find a set such
that
Now, note that
Denote these as
respectively. By Lemma 3.8, there exist subsets of such that Let contain
the subscripts of corresponding
to the elements in , and form
by exchanging the labels of
and for all and leaving all remaining labels
the same. This once again assigns a weight of to each -sided face, but now the weights of the
two -sided faces are equal,
resulting in a face magic
labeling.
3.4. Type
When is odd, we have a -antimagic labeling of type by Theorem 3.4.
One can easily see that such a labeling can be used to form a face-magic
labeling of type . Therefore, we have the
following:
Theorem 3.10. If is odd, then the prism graph admits a type face-magic labeling.
We will therefore focus our attention on the case where is even. We begin with a necessary
condition for a prism to have a face magic labeling of type Once again we will generalize,
proving the result for type
face-magic labelings where is any
nonnegative integer and is
odd.
Theorem 3.11. Let be nonnegative integers such that
is odd and . If the prism graph admits a type face-magic labeling, then
Proof. By way of contradiction, let for some integer , and let have an face magic labeling, with -sided faces having weight and -sided faces having weight Let be the sum of the vertex labels,
be the sum of the region
labels, and be the sum of all
labels. By summing the weight of all faces, we obtain the equality
Thus, since is even, is
also even. Furthermore, since is odd, it follows that
must be an
even integer. However, ,
which is odd. This is a contradiction, and therefore
Therefore, we see that if is
even and has a type face-magic labeling, then We will now
demonstrate that such labelings exist.
The proof of the next theorem was constructed using a type edge-magic total labeling of given by Freyberg in [2]. Let and be such a labeling. Then we know
for all ,
where the arithmetic is performed modulo By assigning the label to the face and arbitrarily assigning
the two labels in to the
vertices and in we instantly get a labeling of the vertices and -sided faces of with the property that the weight of
a -sided face is for all However, the two -sided faces of need not have equal weight. We have
remedied this in the proof of the next theorem by carefully partitioning
into pairs such
that
Theorem 3.12. If
, then the prism
graph admits a type face-magic labeling.
Proof. Let for
some integer If or , the corresponding labelings can be
found in Figure 3. So we
assume and we describe a
labeling as follows. Let and
Figure 3 Type face-magic labelings of
Now that the face labels have been assigned, we define the vertex
labels in the following table.
1
2
3
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 This will be important
next.
We proceed by checking the face weights. We begin with the two -sided faces. We have
Therefore, By
the discussion immediately preceding this theorem, we know for Hence, is a face-magic labeling of type
and the proof is
complete.
3.5. Type
Once again, when is odd we
have a -antimagic labeling of type
by Theorem 3.7, which easily leads to a
face-magic labeling of type . We therefore conclude the
following:
Theorem 3.13. If is odd, then the prism graph admits a type face-magic labeling.
We can use a different approach to show that this is also true when
is even.
Theorem 3.14. If is even, then the prism
graph admits a type face-magic labeling.
Proof. If the
labeling is shown in Figure 4. Therefore
we let , and an edge-magic total labeling of Then there is some integer such that for
every Furthermore,
in the constructions provided in [5], the element is always assigned as an edge label.
Now we define a type
labeling as follows.
Let and for We have used the labels
Since the element was assigned
to an edge of under the
edge-magic total labeling , the
labeling assigns the element
to a face for some
Figure 4 A type face-magic labeling of
The labeling can be completed from a magic rectangle in the following way. First,
add to every entry in Necessarily, the column sums are and the row sums are WLOG, we may assume the
first column of is . Let and . Now, form an
arbitrary bijection between the remaining columns of to the pairs for so
that the first label in each pair is always taken from the first row of
Finally, complete the
construction by swapping the labels of and so that and
Clearly, is a bijection, so
it remains to check the weights. We begin with the two -sided faces. We have, and
Finally, let be a -sided face. Then and we have
Therefore, is face-magic
with and Since , we have proved the claim.
3.6. Type
The generalized prism graph, was
investigated by Baca in [1]. He proved the following.
Theorem 3.15 (Bacaetal. [1])
The generalized prism graph
admits a type face-magic
graph whenever and
By corollary of Theorem 3.15, we
know admits a type face-magic graph whenever Therefore, we could simply
provide labelings for the cases
and 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 , then the prism graph admits a type face-magic labeling.
Proof. If the
labeling is shown in Figure 5. Let
, and an edge-magic total labeling of Then there is some integer such that for
every Define a type
labeling as follows.
Figure 5 Type face-magic labeling of
Let and for We have used the labels
WLOG, we may assume
for some
The labeling can be completed from a magic rectangle in the following way. First,
add to every entry in Necessarily, the column sums are and the row sums are WLOG, we may assume the
first column of is . Let and . Now, form an
arbitrary bijection between the remaining columns of to the pairs for and for so
that the first label in each pair is always taken from the first row of
Finally, complete the
construction by swapping the labels of and so that and
Clearly, is a bijection, so
it remains to check the weights. We begin with the two -sided faces. We have, and
Finally, let be a -sided face. Then and we have
Therefore, is face-magic
with and Since , we have proved the claim.
4. General
Now we turn our attention to the case where 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 admit face-magic labelings of types
and Then also admits a face-magic labeling of
type
Lemma 4.2 (Lih [6]). Let be
nonnegative integers. If admits a
type face-magic labeling,
then also admits a type 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 for nonnegative . 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 admits face-magic
labelings of type for all
, type for all , type for all , and type for .
Proof. The type and
face-magic labelings can be found by combining face-magic labelings of
types and each of which exist for all
The type face-magic labeling for follows from combining
face-magic labelings of types and
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 , then the prism
graph admits a type face-magic labeling.
Proof. This is true for by Lemma 4.3. Therefore, we
restrict to odd The labeling
corresponding to can be found
in Figure 6. Therefore let and let be given by for , and
Figure 6 A type face-magic labeling of
Note that the labels assigned to the vertices form the set , and the labels assigned to vertices form the set . These sum to and respectively.
Therefore, we see that the two -sided faces each have a weight of . (In the case the first line of the label for
is ignored. Furthermore,
note that and Therefore the
labels assigned to vertices are
, which sum to . Thus the same
argument holds.) It can be verified that each -sided face has a weight of . Thus, is a type face magic labeling of
Lemma 4.5. If then the prism graph admits a type face-magic labeling.
Proof. The columns of a magic rectangle form a face-magic labeling of type for odd . Therefore, we focus on the case where
Let with odd, and let be given by
Let be the
projections maps, let be the
image of under , let , and let
. We
observe that are each
injections, and , and In addition,
for all . Now, note that for all
positive , and for all odd
. Therefore, for some . Let Note that
We now form our labeling
as follows:
For , For ,
Lemma 4.6. If is odd, then the prism graph admits a type face-magic labeling.
Proof. Let .
Begin by considering the function given by
One can note that the sums of elements in sum to for and for . These form a set of
consecutive integers from to
. A face-magic labeling of can then be formed by taking a -antimagic labeling of type and assigning labels to the faces of in complementary fashion.
We are now prepared to state and prove the generalization of Theorem
3.1.
Theorem 4.7. Let be nonnegative integers, and let
The prism graph admits a face-magic labeling of type
if and only if is not
(i) for any
,
(ii) for odd
,
(iii) for any
odd , and .
Proof. First note that the nonexistence of type 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 , as well as the
equivalence class of By
Theorem 3.1 and Lemma 4.2, we only need to consider the
following cases:
Case 1. are
even, is odd
If a face-magic labeling
is given by the type
face-magic labeling given in Lemma 4.3 and the application
of Lemma 4.2. If and then this is the case
with odd and for which no
face-magic labeling exists. Otherwise if , and , then a
face-magic labeling is obtained by the type and face-magic labelings given in
Lemmas 4.4, 4.5 and the application of Lemma 4.2.
Case 2. are
odd, are even
If then this is the case
for odd and no face-magic labeling exists.
Otherwise, a face-magic labeling is given by the type and face-magic labelings given in
Lemmas 4.3, 4.6 and the
application of Lemma 4.2.
Case 3. are
odd, is even,
If , then this is the case
with odd and for which no
face-magic labeling exists. Otherwise, a face-magic labeling is given by
the type 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 face-magic labelings in Theorem
3.16. When is even, the construction in the proof
of Theorem 3.16 is similar to combining a
type face-magic labeling
with a type face-magic
labeling using Lemma 4.1. When is odd, a type face-magic labeling can also be
obtained by combining a type face-magic labeling with a type
face-magic labeling.
However, given the lack of elegance in the given face-magic labeling, the
construction in the proof of Theorem 3.16
is here much preferred for odd .
On a related note, an improved construction of the type 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 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
refer to the disjoint union of
copies of .
Problem 5.1. Can the ordered tuples for which the generalized
prism admits a type face-magic labeling be completely
determined?
Problem 5.2. Can the ordered tuples for which some embedding of
the disjoint union admits a
type face-magic labeling be
completely determined?
References:
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.