Labeling Grids

Douglas S. Jungreis and Michael Reid Department of Mathematics University of California, Berkeley Berkeley, California 94720

September 17, 1992

Abstract. We investigate the existence of α-valuations and sequential labelings for a variety of grids in the plane, on a cylinder and on a torus.

1. Introduction. A connected graph with v vertices and e edges is called graceful if it is possible to label the vertices x with distinct integers f(x) in {0, 1, 2, …, e} so that when each edge, xy, is labeled |f(x) − f(y)|, the resulting edge labels are distinct (and thus form the entire set {1, 2, 3, …, e}).

A graceful labeling f is called an α-valuation if there is an integer k such that for any edge xy, either f(x) ≤ k < f(y) or f(y) ≤ k < f(x). Since some edge xy is labeled |f(x) − f(y)| = 1, the integer k is uniquely determined by the α-valuation, and is said to characterize the labeling.

Also, if f is an α-valuation of the graph G, characterized by k, then note that G is bipartite on the vertex sets X = {x ∈ V | f(x) > k} and Y = {x ∈ V | f(x) ≤ k}. This notation will be used throughout the paper.

Graham and Sloane [7] call a connected graph with v vertices and e edges harmonious if its vertices x may be labeled with distinct elements f(x) of Z/eZ so that when edge xy is labeled f(x) + f(y), the resulting edge labels are distinct and thus form the entire set Z/eZ. (If the graph is a tree, i.e. v = e + 1, then one vertex label may be repeated.)

Grace [5,6] calls a connected graph with v vertices and e edges sequential if its vertices x may be labeled with distinct integers f(x) in {0, 1, …, e−1} so that when edge xy is labeled f(x) + f(y), the resulting edge labels form a block of e consecutive integers. If the graph is a tree, then e may be used as a vertex label. Any sequential labeling induces a harmonious labeling by reducing the labels modulo e. Although it seems likely that there are harmonious graphs which are not sequential, there is no known example of such a graph.

In this paper, we find α-valuations and sequential labelings for a variety of graphs of the form P_{m} × P_{n}, C_{m} × P_{n} and C_{m} × C_{n}, where P_{n} is a path on n vertices, and C_{n} is a cycle on n vertices (n > 2). Such graphs can be represented as grids in the plane, on a cylinder, or on a torus. Table 1 summarizes our results. Note that all negative results for α-valuations follow simply because these graphs are not bipartite.

Table 1: Summary of Results

Graph  α-valuation sequential
P_{2m} × P_{2n}  Yes  Yes^{∗}
P_{2m} × P_{2n+1}  Yes  Yes
P_{2m+1} × P_{2n+1}  Yes  Yes
C_{4m} × P_{2n}  Yes  Yes^{∗}
C_{4m} × P_{2n+1}  Yes  Yes
C_{4m+2} × P_{2n}  Yes  Yes

C_{4m+2} × P_{2n+1}

C_{2m+1} × P_{n}  No  Yes
C_{4m} × C_{4n}  Yes  †
C_{4m} × C_{4n+2}  Yes  †
C_{4m} × C_{2n+1}  No

C_{4m+2} × C_{4n+2}

C_{4m+2} × C_{2n+1}  No  No
C_{2m+1} × C_{2n+1}  No  No

* except for (m, n) = (1, 1)

† C_{4} × C_{2n} is sequential for n > 1

Some work with grids has already been done. Graham and Sloane [7] proved that all C_{2m+1} × P_{n} are harmonious and Grace [5] has shown these graphs are also sequential.

Maheo [9] has shown that the graphs P_{2} × P_{n} and C_{4} × P_{n} have αvaluations, Graham and Sloane [7] have shown that P_{2}×P_{n} are harmonious, Frucht and Gallian [1] have shown that P_{2} × C_{2n} have α-valuations and P_{2} × C_{2n+1} are graceful, Gallian, Prout and Winters [4] have shown that P_{2} × C_{2n} are sequential for n > 2, and Huang and Skiena [8] have shown that C_{4m+2} × P_{2n+1} are graceful.

In his survey paper on graph labelings, Gallian [2] opined that among the open problems on graph labeling he considered those involving grids to be the most attractive. Gallian again singled out these problems for attention in the Unsolved Problems section of the American Mathematical Monthly [3].

2. Relationship between α-valuations and sequential labelings. In [5,6], Grace uses the following construction to prove the corollary to this useful theorem.

Theorem 2.1. If the graph G, with e edges, has an α-valuation, then the vertices x of G can be labeled with distinct integers f(x) in {0, 1, 2, …, e} so that the set of induced labels on edges xy, {f(x) + f(y)} is a block of e consecutive integers.

Proof. Suppose g is an α-valuation of G, characterized by k. Recall that G is bipartite on X = {x | g(x) > k} and Y = {x | g(x) ≤ k}. Define f by

f(x) = \{ \begin{matrix}g(x) & if x ∈ X \\ k − g(x) & if x ∈ Y \end{matrix}

Note that f is injective. Also, if xy is an edge, x ∈ X, y ∈ Y, then

f(x) + f(y) = g(x) + k − g(y) = k + |g(x) − g(y)| ,

so the set of edge labels is {k + 1, k + 2, …, k + e} as desired. □

Corollary 2.2. If a tree has an α-valuation, then it is sequential.

2.3. Bipartite label-shifting. Let G be a graph that is bipartite on X and Y, and suppose we have some labeling, f, of the vertices of G, that induces the labels f(x) + f(y) on the edges xy. If we define a new labeling by incrementing the labels of vertices in X by a and incrementing the labels of vertices in Y by b, the induced edge labels have all been incremented by a + b. Thus, this type of change does not affect whether or not the edge labels are distinct consecutive integers (or if they form a complete residue system modulo e), but it may well affect whether or not the vertex labels are distinct and in the desired range.

[figure: α-valuation; “pre-sequential”; sequential; 0; 7; 8; 2; 6; 4; 3; 3; 7; 8; 1; 6; 4; 0; 3; 5; 6; 1; 4; 2; 0; 7; 8; 5; 6; 4; 2; 3; 1; 10; 11; 8; 9; 7; 5; 6; 4; 8; 9; 6; 7; 5; 3; 4; 2]

This construction, when used together with Grace’s construction, can be a powerful tool. For example, start with an α-valuation of C_{4}^{(2)}, the one point union of two copies of C_{4}, apply Grace’s construction, and then subtract 2 from each boxed vertex to get a sequential labeling, as above.

3. Planar Grids. We begin with a simple remark that has far-reaching applications. Suppose the graph G has an α-valuation characterized by k. Recall G is then bipartite on the vertex sets X and Y, as defined in Section 1. If we add x to the labels of vertices in X, and y to the labels of vertices in Y, then the edge labels become the integers from x − y + 1 through x − y + e (if x ≥ y).

Theorem 3.1. The graph P_{m} × P_{n} has an α-valuation.

Proof. Let J denote the α-valuation of P_{m}

0, m − 1, 1, m − 2, 2, m − 3, …

and let R(x) be the labeling obtained from J by adding (2mn−2m−n+1)−x to the higher labels, x to the lower labels. Let K = (m − 1) − J denote the α-valuation of P_{m}

m − 1, 0, m − 2, 1, m − 3, 2, …

and let S(x) be the labeling obtained from K by adding (2mn − 2m − n + 2) − x to the higher labels, and x to the lower labels.

Now, consider P_{m} × P_{n} to be n juxtaposed copies of P_{m}. Label the (2k + 1)^{st} copy of P_{m} with R(k(2m − 1)), the 2k^{th} copy with S(k(2m − 1) + (1 − m)).

The edge labels of the r^{th} copy of P_{m} are the integers from (2mn − n + 1) − r(2m − 1) through (2mn − n + 1) − r(2m − 1) + (m − 2), and the labels of the edges joining the r^{th} and (r + 1)^{st} copies of P_{m} are the integers from (2mn−n+1)−(r+1)(2m−1)+(m−1) through (2mn−n+1)−r(2m−1)−1. It follows that this is a graceful labeling, and inspection shows that it is also an α-valuation. □

This labeling is particularly nice, as the edges are labeled consecutively. See labelings of P_{4} × P_{5} and P_{4} × P_{6} below:

α-valuation of P_{4} × P_{5} 30 5 23 12 16 1 27 8 20 15 31 4 24 11 17 0 28 7 21 14  ^{α-valuation of P_{4} × P_{6} 37 5 30 12 23 19 1 34 8 27 15 20 38 4 31 11 24 18 0 35 7 28 14 21}

Also nice is the following corollary.

Corollary 3.2. The graph P_{2m} × P_{2n+1} is sequential.

Proof. Apply Grace’s construction to the α-valuation given above of P_{2m} × P_{2n+1}, and subtract 2m from the higher vertex labels. A routine verification shows that this is indeed a sequential labeling. □

Again, the edges are labeled consecutively; we illustrate for P_{4} × P_{5} below:

α-valuation of P_{4} × P_{5} 30 5 23 12 16 1 27 8 20 15 31 4 24 11 17 0 28 7 21 14  ^{sequential labeling of P_{4} × P_{5} 26 10 19 3 12 14 23 7 16 0 27 11 20 4 13 15 24 8 17 1}

A slight variation will give a sequential labeling of P_{2m} × P_{2n}. However, it is easy to see that P_{2} × P_{2} = C_{4} is not harmonious. The following result shows that this is the only exception among these graphs.

Theorem 3.3. If n > 1, then P_{2m} × P_{2n} has a sequential labeling.

Proof. Start with the α-valuation of P_{2m} ×P_{2n} given in 3.1, and subtract 1 from each vertex label of the 2n^{th} copy of P_{2m}. This doesn’t change any edge labels of the 2n^{th} copy of P_{2m}, and permutes adjacent pairs of edges joining the last two copies of P_{2m}. Since no other edge labels are affected, this is also an α-valuation (characterized by a different k).

Now apply Grace’s construction, and subtract 2m from the higher vertex labels. It is straightforward to check that this is a sequential labeling. □

We illustrate the process for P_{6} × P_{4}:

α-valuation of P_{6} × P_{4} 36 8 25 19 2 31 13 20 37 7 26 18 1 32 12 21 38 6 27 17 0 33 11 22  ^{new α-valuation of P_{6} × P_{4} 36 8 25 18 2 31 13 19 37 7 26 17 1 32 12 20 38 6 27 16 0 33 11 21}  ^{sequential labeling of P_{6} × P_{4} 30 10 19 0 16 25 5 13 31 11 20 1 17 26 6 14 32 12 21 2 18 27 7 15}

Theorem 3.4. The graph P_{2m+1} × P_{2n+1} has a sequential labeling.

Proof. Partition the vertices of P_{2m+1} × P_{2n+1} into the sets T, U_{1}, U_{2}, U_{3}, …, U_{m} and V as shown.

[figure: ⋯; ⋯; ⋯; ⋮; ⋮; ⋮; ⋮; ⋮; ⋮; ⋮; ⋯; ⋯; ⋯; ⋯; ⋯; ⋮; ⋮; ⋮; ...; T; U_{1}; U_{2}; ⋮; U_{m}; V]

Label the vertices of T with x−3n, x−3n+1, x−3n+2, …, x−2n−1, where x = 4mn + m + 2n. Label U_{1} as follows

0  2  4  2n
x  1  x + 2  3  x + 4 ⋯  2n − 1  x + 2n
x + 1  x + 3  x + 2n − 1

and label U_{i} by adding (i−1)(4n+1) to corresponding vertices of U_{1}. Label the vertices of V with x − 2n, x − 2n + 1, x − 2n + 2, …, x − n.

The edges of the graph are then labeled consecutively in a zigzag pattern, which is illustrated by P_{5} × P_{7}. □

sequential labeling of P_{5} × P_{7} 26 46 27 48 28 50 29 45 14 47 16 49 18 51 13 33 15 35 17 37 19 32 1 34 3 36 5 38 0 23 2 24 4 25 6

Corollary 3.5. All grids P_{m} × P_{n} except P_{2} × P_{2} are sequential.

4. Cylindrical Grids. Let L represent the α-labeling of C_{4m}: 0, 4m, 1, 4m − 1, …, m, 3m − 1, m + 1, …, 2m. Note that the label 3m is unused. Suppose X and Y are the two vertex-subsets of the bipartite graph C_{4m} (as described above). Define L(x, y) to be the vertex-labeling obtained from L by adding x to each label in X and y to each label in Y. Define L(x, y; r) to be the labeling obtained from L(x, y) by rotating the labeling by r vertices (to the right, i.e. a, b, c, d rotated through 1 vertex yields d, a, b, c). Notice that the edge-labels of L(x, y; r) range from (1 + x − y) to (4m + x − y).

Theorem 4.1. The graph C_{4m} × P_{n} has an α-valuation.

Proof. Label the n copies of C_{4m} with: L(8mn−8m, 0; 0), L(8mn−12m, 4m; 1), L(8mn − 16m, 8m; 0), …, L(4mn − 4m, 4mn − 4m; k), where k = 0 if n is odd, and k = 1 if n is even. Notice that every second labeling is rotated by 1, and in each case x is decreased by 4m while y is increased by 4m. The i^{th} copy of C_{4m} includes the edges (8mn − 8mi) + 1 through (8mn − 8mi) + 4m. The edges that join the i^{th} and (i + 1)^{st} copies of C_{4m} include the edges (8mn−8mi)+(4m+1) through (8mn−8mi)+8m. Thus the edges of the graph cover the integers from 1 to (8mn − 4m) as desired. By inspection, the labeling is an α-valuation. □

The labeling of C_{4} × P_{5} is shown:

α-valuation of C_{4} × P_{5} 34 5 26 13 18 1 32 9 24 17 36 4 28 12 20 0 30 8 22 16

The following result employs an important technique that will be used several times.

Theorem 4.2. The graph C_{4m} × P_{2n+1} has a sequential labeling.

Proof. Start with the α-valuation given in 3.1 of P_{2n+1} ×P_{4m}. Transpose the graph and its labeling, as though it were a matrix. This gives an α-valuation of P_{4m} × P_{2n+1}. Now apply Grace’s construction, subtract 8mn + 2m − n from the higher labels, and add 8mn + 2m − 3n to the lower labels to get a sequential labeling of P_{4m} × P_{2n+1}.

Connect the 4m^{th} copy of P_{2n+1} to the first, so our graph becomes C_{4m}× P_{2n+1}. These new edges have the same labels as those edges connecting the 2m^{th} and (2m + 1)^{st} copy of P_{2n+1}.

Let U denote the first 2m copies of P_{2n+1} and the edges between them. The labels of edges in U are those integers from A through B. The labels of edges with one vertex in U are the integers from A − 2n − 1 through A − 1, each occurring twice. Now add 2n + 1 to the higher labels in U. (Since P_{4m} × P_{2n+1} is not a tree, and since we’ve added 2n + 1 edges to it, the vertex labels stay in range for a sequential labeling.) The edges contained in U now have labels A + 2n + 1 through B + 2n + 1, and of the two edges that used to have the same label, one has been increased by 2n + 1, the other unchanged. Therefore, the edges with one vertex in U now have labels A − 2n − 1 through A + 2n, and we have a sequential labeling. □

α-valuation P_{4} × P_{5} 18 14 17 15 16 9 22 10 21 11 27 5 26 6 25 0 31 1 30 2  ^{sequential labeling of P_{4} × P_{5} 2 13 1 12 0 18 6 17 5 16 11 22 10 21 9 27 15 26 14 25}  ^{sequential labeling of C_{4} × P_{5} 2 13 1 12 0 18 6 17 5 16 11 27 10 26 9 32 15 31 14 30}

The same technique is used for the following result.

Theorem 4.3. If m > 1, then C_{4m} × P_{2n} is sequential.

Proof. Start with the α-valuation of P_{2n}×P_{4m} given in 3.1, and transpose it, as in 4.2, to get an α-valuation of P_{4m} × P_{2n}. Add 1 to each label of the (4m − 1)^{st} copy of P_{2n}. Similar to the proof of 3.3, the only affected edge labels are those joining the (4m − 2)^{nd} and (4m − 1)^{st} copies of P_{2n}, and those joining the (4m−1)^{st} and 4m^{th} copies. Furthermore, these labels are permuted in adjacent pairs, so this is still an α-valuation.

Now apply Grace’s construction, and subtract 2n from the higher labels to get a sequential labeling. Join the first copy of P_{2n} to the last, to get C_{4m} × P_{2n}, and add 2n to the higher labels of the first 2m copies of P_{2n}. As before, this gives a sequential labeling of C_{4m} × P_{2n}. □

α-valuation of P_{8} × P_{4} 28 25 27 26 21 31 22 30 35 18 34 19 14 38 15 37 42 11 41 12 7 45 8 44 49 4 48 5 0 52 1 51  ^{new α-valuation of P_{8} × P_{4} 28 25 27 26 22 32 23 31 35 18 34 19 14 38 15 37 42 11 41 12 7 45 8 44 49 4 48 5 0 52 1 51}^{sequential labeling of P_{8} × P_{4} 24 1 23 0 4 28 3 27 31 8 30 7 12 34 11 33 38 15 37 14 19 41 18 40 45 22 44 21 26 48 25 47}  ^{sequential labeling of C_{8} × P_{4} 24 1 23 0 4 28 3 27 31 8 30 7 12 34 11 33 42 15 41 14 19 45 18 44 49 22 48 21 26 52 25 51}

In light of Grace’s construction, it is not surprising to find that this technique also comes in handy in the realm of α-valuations.

Theorem 4.4. The graph C_{4m+2} × P_{2n} has an α-valuation.

Proof. Transpose the α-valuation of P_{2n} × P_{4m+2} given in 3.1, to get an α-valuation of P_{4m+2} × P_{2n}. Now subtract 1 from each label of the (4m + 2)^{nd} copy of P_{2n}. We’ve seen earlier that this is also an α-valuation. Now connect the first copy of P_{2n} to the last, to get C_{4m+2} × P_{2n}, and add 2n to the higher labels of the first 2m + 1 copies of P_{2n}. Similar to before, this gives an α-valuation of C_{4m+2} × P_{2n}. □

We also have the following result.

Corollary 4.5. The graph C_{4m+2} × P_{2n} is sequential.

Proof. Apply Grace’s construction to the α-valuation given above, and subtract 2n from the higher labels to get a sequential labeling. □

We illustrate for C_{6} × P_{4}:

α-valuation of P_{6} × P_{4} 21 18 20 19 14 24 15 23 28 11 27 12 7 31 8 30 35 4 34 5 0 38 1 37  ^{new α-valuation of P_{6} × P_{4} 20 17 19 18 14 24 15 23 28 11 27 12 7 31 8 30 35 4 34 5 0 38 1 37}

α-valuation of C_{6} × P_{4} 20 17 19 18 14 24 15 23 28 11 27 12 7 35 8 34 39 4 38 5 0 42 1 41  ^{sequential labeling of C_{6} × P_{4} 16 1 15 0 4 20 3 19 24 7 23 6 11 31 10 30 35 14 34 13 18 38 17 37}

Theorems 4.2 and 4.3 show that all graphs C_{4n} × P_{m} are sequential, except for C_{4} × P_{2m}. In fact, Graham and Sloane [7] used an exhaustive computer search to show that C_{4} × P_{2} is not even harmonious. However, our next result shows that this is the sole exception among these graphs.

Theorem 4.6. If n > 2, then C_{4} × P_{n} is sequential.

Proof. Let M denote the labeling of C_{4} by 3, 4n − 1, 5, 4n, and N the labeling 0, 4n−5, 2, 4n−6. Let M(x) denote the labeling obtained from M by adding x to the vertex labels, and let M(x; t) be the labeling obtained by rotating M(x) through t vertices (as in the proof of Theorem 4.1). Define N(x; t) similarly.

Now, label the first copy of C_{4} N(0; 0), the last N(4(n − 1); n + 1). Label the r^{th} copy (1 < r < n) M(4(r − 2); r − 1).

The edge labels on the r^{th} copy of C_{4} are 8r+4n−14 through 8r+4n−11, and the edges joining the r^{th} and (r + 1)^{st} copies have labels 8r + 4n − 10 through 8r + 4n − 7. One readily checks that the vertex labels are distinct and in the desired range, so this is a sequential labeling. □

We illustrate for C_{4} × P_{5} and C_{4} × P_{6}:

sequential labeling of C_{4} × P_{5} 14 5 23 11 31 2 19 7 28 16 15 3 24 13 30 0 20 9 27 18  ^{sequential labeling of C_{4} × P_{6} 18 5 27 11 36 20 2 23 7 32 17 38 19 3 28 13 35 22 0 24 9 31 15 39}

Graham and Sloane [7] note that any harmonious labeling of C_{2m+1} extends to a harmonious labeling of C_{2m+1} × P_{n}. The same is true for sequential labelings, as noted by Grace [5]. Indeed, if Q is any sequential labeling of C_{2m+1}, (for example, 0, m + 1, 1, m + 2, 2, …, m − 1, 2m, m), and Q(x; t) defined as in 4.6, then Q(0; 0), Q(2m + 1; 1), Q(2(2m + 1); 0), Q(3(2m + 1); 1), … is a sequential labeling of C_{2m+1} × P_{n}. Illustrated is C_{5} × P_{6}:

sequential labeling of C_{5} × P_{6} 2 9 12 19 22 29 4 6 14 16 24 26 1 8 11 18 21 28 3 5 13 15 23 25 0 7 10 17 20 27

5. Toroidal Grids. These graphs seem to be more challenging, and we have settled very few cases.

Theorem 5.1. The graph C_{4m} × C_{4n} has an α-valuation.

Proof. Start with the α-valuation of C_{4m} × P_{4n} given in 4.1. Connect the first and last copies of C_{4m} to get the graph C_{4m} × C_{4n}. Now, add 4m to the higher labels in the first 2n copies of C_{4m} to get an α-valuation. □

We illustrate for C_{4} × C_{8}:

α-valuation of C_{4} × P_{8} 58 5 50 13 42 21 34 29 1 56 9 48 17 40 25 32 60 4 52 12 44 20 36 28 0 54 8 46 16 38 24 30  ^{α-valuation of C_{4} × C_{8} 62 5 54 13 42 21 34 29 1 60 9 52 17 40 25 32 64 4 56 12 44 20 36 28 0 58 8 50 16 38 24 30}

A slight variation will work for C_{4m} × C_{4n+2}.

Theorem 5.2. The graph C_{4m} × C_{4n+2} has an α-valuation.

Proof. Start with the α-valuation given in 4.1 of C_{4m} × P_{4n+2}, except label the (4n+2)^{nd} copy of C_{4m} with L(16mn+4m, 16mn+4m; −1) instead of L(16mn+4m, 16mn+4m; 1). As in 4.1, this is also an α-valuation. Now, connect the first and last copies of C_{4m}, to get C_{4m} ×C_{4n+2}, and add 4m to the higher labels in the first 2n+1 copies of C_{4m}. This gives an α-valuation of C_{4m} × C_{4n+2}. □

We illustrate for C_{4} × C_{6}:

original α-valuation of C_{4} × P_{6} 42 5 34 13 26 21 1 40 9 32 17 24 44 4 36 12 28 20 0 38 8 30 16 22  ^{new α-valuation of C_{4} × P_{6} 42 5 34 13 26 20 1 40 9 32 17 22 44 4 36 12 28 21 0 38 8 30 16 24}  ^{α-valuation of C_{4} × C_{6} 46 5 38 13 26 20 1 44 9 32 17 22 48 4 40 12 28 21 0 42 8 30 16 24}

Our only families of sequential toroidal grids come from the sequential labeling of C_{4} × P_{n} given in 4.6.

Theorem 5.3. The graph C_{4} × C_{4n} is sequential.

Proof. Start with the sequential labeling of C_{4}×P_{4n} given in 4.6. Connect the first copy of C_{4} to the last copy, and add 4 to the higher labels of the last 2n copies of C_{4} to get a sequential labeling of C_{4} × C_{4n}. □

sequential labeling of C_{4} × P_{8} 27 3 36 13 43 19 52 28 2 31 7 40 17 47 23 55 26 5 35 11 44 21 51 30 0 32 9 39 15 48 25 54  ^{sequential labeling of C_{4} × C_{8} 27 3 36 13 47 19 56 28 2 31 7 40 17 51 23 59 26 5 35 11 48 21 55 30 0 32 9 39 15 52 25 58}

A slight twist will give us a sequential labeling of C_{4} × C_{4n+2}.

Theorem 5.4. The graph C_{4} × C_{4n+2} is sequential.

Proof. Start with the sequential labeling of C_{4} × P_{4n+2} given in 4.6, and rotate the labels of the first two copies of C_{4} through 2 vertices. It is easily verified that this is also a sequential labeling. Now, join the first and last copies of C_{4}, and add 4 to the higher labels of the last 2n + 1 copies of C_{4}. This gives a sequential labeling of C_{4} × C_{4n+2}. □

We illustrate for C_{4} × C_{6}:

original sequential labeling of C_{4} × P_{6} 18 5 27 11 36 20 2 23 7 32 17 38 19 3 28 13 35 22 0 24 9 31 15 39  ^{new sequential labeling of C_{4} × P_{6} 19 3 27 11 36 20 0 24 7 32 17 38 18 5 28 13 35 22 2 23 9 31 15 39}  ^{sequential labeling of C_{4} × C_{6} 19 3 27 11 40 20 0 24 7 36 17 42 18 5 28 13 39 22 2 23 9 35 15 43}

6. Negative results. In our opening remarks, we note that if G has an α-valuation, then G is bipartite. This necessary condition is responsible for the four negative results for α-valuations. There is also a necessary condition for some graphs to be graceful.

Theorem 6.1. Suppose G is any graph with a graceful labeling, and let e_{1}, e_{2}, …, e_{n} be any edge-cycle of G. Then we can divide the edges e_{1} through e_{n} into two subsets such that the sum of edge-labels of one subset equals that of the other subset.

Proof. Let v_{i} be the vertex shared by e_{i} and e_{i+1} (where e_{n+1} = e_{1}), and let |v| and |e| be the labels on v and e respectively. Then |v_{2}| = |v_{1}| ± |e_{2}|, |v_{3}| = |v_{2}| ± |e_{3}|, etc. Combining these equations, we get |v_{1}| = |v_{1}| ± |e_{2}| ± |e_{3}| ± ⋯ ± |e_{1}|, so 0 = ± |e_{1}| ± |e_{2}| ± ⋯ ± |e_{n}|. Those edges preceded by a plus sign in this equation form one subset; the other edges form the second subset. □

Corollary 6.2. Let G and e_{1}, …, e_{n} be as described in Theorem 6.1. Then ∑_{i=1}^{n} |e_{i}| is an even integer.

The following corollary was first given by Rosa [10], however we provide an alternate proof.

Corollary 6.3. Let G be any graph with a graceful labeling. Suppose G has e edges, and suppose every vertex of G has an even valence. Then either e ≡ 3 mod 4 or e ≡ 0 mod 4.

Proof. G has an Eulerian cycle, so by Corollary 6.2, the sum of the edges is even. This sum is e(e + 1)/2, so e ≡ 3 mod 4 or e ≡ 0 mod 4. □

Corollary 6.4. If m and n are odd, then C_{m} × C_{n} is not graceful.

The only general necessary condition for a graph to be harmonious is due to Graham and Sloane [7]. We include the proof for completeness.

Theorem 6.5. If the harmonious graph G has an even number e of edges, and for some k ≥ 0, the degree of each vertex in G is a multiple of 2^{k}, then e is a multiple of 2^{k+1}.

Proof. Let f be a harmonious labeling, let e = 2e′, let v(x) denote the degree of the vertex x and let v(x) = 2^{k}v′(x). Then we have

e′ ≡ ∑_{n=1}^{e} n ≡ ∑_{xy∈E(G)} f(xy) = ∑_{xy∈E(G)} f(x) + f(y) =

∑_{x∈V (G)} v(x)f(x) = 2^{k} ∑_{x∈V (G)} v′(x)f(x) mod e.

Thus, 0 ≢ e′ ≡ 2^{k} ∑ v′(x)f(x), while 0 ≡ 2e′ ≡ 2^{k+1} ∑ v′(x)f(x). Therefore, the element ∑_{v∈V (G)} v′(x)f(x) has order exactly 2^{k+1} in Z/eZ, whence 2^{k+1} divides e. □

Corollary 6.6. If 4 does not divide mn, then C_{m} ×C_{n} is not harmonious (and hence not sequential).

7. Conclusion. It remains unknown whether or not several classes of grids have various labelings (see gaps in Table 1). Since we have been unable to complete Table 1, we pose as an open question the determination of the missing entries. Although C_{4} × C_{3}, C_{4} × C_{5}, C_{4} × C_{7}, C_{4} × C_{9} and C_{6} × C_{3} do not have α-valuations, Eric Wepsic has found graceful labelings for them with the aid of a computer. The sequential labeling of C_{3} × C_{4} shown below was found by the authors by trial and error. Likewise, the graphs C_{2m+1}×P_{n} do not have α-valuations but Huang and Skiena [8] have found graceful labelings for them.

C_{3} × C_{4} is sequential 6 3 8 14 4 9 15 12 0 5 10 7

To this point, numerous papers have been devoted to labeling various types of graphs, yet few results can be easily generalized. For instance Rosa’s criterion (see Corollary 6.3) is the only known necessary condition for existence of graceful labelings, and no conditions are known to be sufficient. Of more interest than the completion of Table 1 would be the development of some general theory of labeling graphs.

Acknowledgment. The authors wish to thank Professor Joseph A. Gallian for suggesting this problem and assisting with the preparation of this paper. The work was done at the University of Minnesota, Duluth under his supervision and was supported by an NSF-RUI Grant (#8407498).

References

1. Roberto Frucht and Joseph A. Gallian, Labeling prisms, Ars Combinatoria 26 (1988) 69–82. MR 90a:05178

2. Joseph A. Gallian, A survey–recent results, conjectures and open problems in labeling graphs, Journal of Graph Theory 13 (1989), no. 4, 491–504. MR 90k:05132 3. Joseph A. Gallian, Open problems in grid labeling, American Mathe-

matical Monthly 97 (1990), no. 2, 133–135.

4. Joseph A. Gallian, John Prout and Steven Winters, Graceful and harmonious labelings of prism related graphs, Ars Combinatoria 34 (1992), 213-222 MR 93i:05112

5. Thomas Peter Grace, Graceful, harmonious, and sequential graphs, Ph.D. Thesis, University of Illinois at Chicago Circle, 1982.

6. Thom Grace, On sequential labelings of graphs, Journal of Graph Theory 7 (1983) 195–201. MR 84m:05075

7. R.L. Graham and N.J.A. Sloane, On additive bases and harmonious graphs, Society for Industrial and Applied Mathematics. Journal on Algebraic and Discrete Methods 1 (1980) 382–404. MR 82f:10067a

8. Jen-Hsin Huang and Steven S. Skiena, Gracefully labeling prisms, Ars Combinatoria 38 (1994), 225-242. MR 96b:05151

9. Maryvonne Maheo, Strongly graceful graphs, Discrete Mathematics 29 (1980), no. 1, 39–46. MR 82j:05093

10. A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (International Symposium, Rome, July 1966) Gordon and Breach, N.Y. and Dunod, Paris (1967) 349–355. MR 36 #6319