Enumerating Families of Labeled Graphs

Christian Barrientos and Sarah Minion Department of Mathematics Clayton State University Morrow, GA 30260 USA

               sarah.m.minion@gmail.com
                chr barrientos@yahoo.com

Abstract

In 1966, Rosa introduced, among others, α- and β-labelings as tools to solve the isomorphic decomposition problem of the complete graph. Ten years later, Sheppard calculated the number of α- and β-labeled graphs with n edges. In this paper we use an extended version of the adjacency matrix of a graph to determine the number of gracefully labeled graphs with n edges; furthermore, we also calculate the number of them with m vertices for every suitable value of m. In addition, we use this technique to determine the number of labeled graphs for other types of labelings as the harmonious, felicitous, and elegant.

1 Introduction

By a graph we mean a finite undirected graph with no loops or multiple edges (for all undefined graph-theoretical terminology see [3, 4]). In addition, graphs considered here have no isolated vertices. By a labeling f of a graph G, of order m and size n, we understand an injective mapping from V (G) into a subset of the non-negative integers. By L_{f} we denote the set of labels f(v_{i}) of the vertices v_{i} of G. The set W_{f} is formed by all the numbers |f(v_{i}) − f(v_{j})| where v_{i}v_{j} is an edge of G.

Now consider a labeling f of a graph G of size n and the following conditions:

(a) L_{f} ⊆ {0, 1, …, n}; (b) W_{f} = {1, 2, …, n};

(c) there exists λ, λ ∈ {0, 1, …, n}, such that for any edge v_{i}v_{j} of the graph G, either f(v_{i}) ≤ λ < f(v_{j}) or f(v_{j}) ≤ λ < f(v_{i}) holds.

A labeling satisfying the conditions (a) and (b) is called a β-labeling (or graceful labeling). If in addition the condition (c) is satisfied, we have an α-labeling.

For every v ∈ V (G), the number f(v) is called the label of v; for every uv ∈ E(G), the number |f(u) − f(v)| is called the weight of uv. When f is a β-labeling we say that G is graceful or it is β-labeled; if f is an α-labeling we say that G is an α-graph or it is α-labeled. The number λ in (c) is called the boundary value of f.

These labelings have been intensively studied since their introduction by Rosa [9] in the mid-sixties. Rosa called them β- and α-valuations, respectively. The term graceful labeling was introduced by Golomb [5] years later to refer to Rosa’s β-valuation, and it is the standard name nowadays. Multiple families of graphs have been proven to be graceful; however, the graceful tree conjecture (that states that every tree is graceful) remains unsolved. For more information about graph labelings, the interested reader is refered to Gallian’s survey [4].

Let G be a graph of order m and size n. It is well-known that if G is graceful, then m − n ≤ 1. Also, if G is an α-graph, then G is bipartite. Suppose that f is a β-labeling of G, then its complementary labeling \overline{f}, defined by \overline{f}(v) = n − f(v), for every v ∈ V (G), is also a β-labeling. This fact can be used to prove that the number of different β-labelings of G is even, except when G ≅ K_{2}.

When f is an α-labeling of G with boundary value λ, the α-labeling f^{−1} of G given by,

f^{−1}(v) = λ − f(v) (mod n + 1),

is called the inverse labeling of f. Thus, depending on the symmetry of the structure of G, the number of different α-labelings of G is a multiple of 4.

In 1976, Sheppard [10] counted the number of different α- and β-labeled graphs with n edges. He used a sequence of integers to represent the labelings, showing the existence of an injective correspondence between the size n and these n-element sequences. Sheppard proved that the number of β-labeled graphs of size n is n!. He also counted the number of α-labeled graphs of size n to be

2 ∑_{λ=0}^{\frac{n−2}{2}}(λ!)^{2}(λ + 1)^{n−2λ}

when n is even, and

2 ∑_{λ=0}^{\frac{n−3}{2}}(λ!)^{2}(λ + 1)^{n−2λ} + (\frac{n − 1}{2})! (\frac{n + 1}{2})!

when n is odd.

In Section 2 we introduce another representation of gracefully labeled graphs which simplifies the attainment of the previous formulas. We also use this representation to count the number of labeled graphs where the labeling used is harmonious, felicitous, or elegant. In Section 3 we determine the exact number of gracefully labeled graphs of size n and order m.

2 Graceful Triangles

Let f be a β-labeling of a graph G of order m and size n. The β-labeled graph G can be described by means of matrices. One such matrix is the graceful matrix A(G) = [a_{ij}], where a_{ij} = 1 if there exists uv ∈ E(G) such that f(u) = i and f(v) = j, and a_{ij} = 0 otherwise, for 0 ≤ i, j ≤ n. These matrices were introduced by Zhi-Zeng [14]. The graceful matrix is just an extension of the adjacency matrix and as this one, it is symmetric and all the elements in the main diagonal equal zero. Therefore, all the characteristics of the β-labeled graph G can be seen in the triangular arrangement formed by the cells a_{ij} of A(G) where i < j, 0 ≤ i ≤ n − 1, and 1 ≤ j ≤ n. We call this arragement the graceful triangle. In Figure 1 we show a β-labeled graph of order 6 and size 10 together with its graceful triangle, where the adjacencies have been represented by dots.

Figure 1: Graceful Triangle

The graceful matrix tool has been used by other authors. Barrientos [1], Zhi-Zeng [14], and Shiue and Lu [11], use it to prove the existence of α- and β-labelings for certain families of graphs. In addition, Haviar and Ivaška [7] use, in their book, a similar tool to count these types of labeled graphs, providing an alternative proof to Sheppard’s result.

In general, for a β-labeled graph G of order m and size n, its graceful triangle contains n diagonals d_{1}, d_{2}, …, d_{n}, where d_{k} is formed by the cells a_{ij} where j −i = n+1−k, 1 ≤ k ≤ n. Thus d_{k} has exactly k cells. Moreover, each diagonal contains exactly one adjencency or dot.

If in a triangular arrangement with n diagonals, every diagonal has one dot, then clearly the arrangement is the graceful triangle of a β-labeled graph of size n. Thus, we can use them to count the number of β-labeled graphs with n edges.

Let d_{1}, d_{2}, …, d_{n} be the diagonals of a triangular arrangement. Since for every 1 ≤ k ≤ n, the diagonal d_{k} has k cells and only one of them can be present, that is, contains a dot, in a graceful triangle, it is possible to construct n! of these triangles, i.e., there are n! β-labeled graphs of size n. Within a graceful triangle, when all the adjacencies are rotated around the axis formed by the cells a_{ij} with i + j = n, the resulting graceful triangle corresponds to the complementary labeling of the original. Furthermore, when an α-labeling f, with boundary value λ, is represented in a triangular arrangement, all the adjacencies lie in a rectangle with corners a_{0n}, a_{0(λ+1)}a_{λ(λ+1)}, a_{λn}. We refer to this rectangle as the rectangle determined by λ. An example of this fact is shown in Figure 2 for an α-graph of size 7 and boundary value 3.

Figure 2: Triangular representation of an α-labeling

Notice that the inverse labeling of f is obtained rotating this rectangle by 180 degrees. This representation of α-labelings is extremely useful to count the number of α-labeled

graphs of size n. In fact, we just need to count the number of possible rectangles and within each rectangle, the number of possible distributions of dots. Using the symmetry we can consider only half of the possible values for λ and multiply by 2. When n is even, the rectangle determined by λ for 0 ≤ λ ≤ \frac{n−2}{2}, is symmetric to the one determined by n−λ−1.

Let f be an α-labeling of G with boundary value λ, where 0 ≤ λ ≤ \frac{n−2}{2}. For k ∈ {1, 2, …, λ}, the diagonals d_{k} and d_{n+1−k} have k cells that can be used to place a dot; thus there are (λ!)^{2} possible distributions of the dots. For k ∈ {λ + 1, λ + 2, …, n − λ}, the diagonals d_{k} have λ + 1 cells where a dot can be placed, thus there are (λ + 1)^{n−2λ} possible distributions of the dots. Hence, there are (λ!)^{2}(λ + 1)^{n−2λ} graphs of even size n that admit an α-labeling with boundary value λ. Taking the sum over all possible values of λ and multiplying by 2, we obtain the number of α-labeled graphs of even size n.

When n is odd, the rectangle determined by λ for 0 ≤ λ ≤ \frac{n−3}{2}, is symmetric to the one determined by n − λ − 1. The only difference with the even case is when λ = \frac{n−1}{2}. In this case the diagonals d_{k} and d_{n+1−k}, for 1 ≤ k ≤ λ, have k cells that can be used to place a dot, i.e., there are (\frac{n−1}{2}!)^{2} possible distributions of the dots. The remaining diagonal, d_{\frac{n+1}{2}} , has \frac{n+1}{2} cells where a dot can be placed. Since

((\frac{n − 1}{2})!)^{2} \frac{n + 1}{2} = (\frac{n − 1}{2})! (\frac{n + 1}{2})!,

we have that there are (λ!)^{2}(λ+1)^{n−2λ} graphs of size n that admit an α-labeing with boundary value λ, 0 ≤ λ ≤ \frac{n−3}{2} and (\frac{n−1}{2})! (\frac{n+1}{2})! with boundary value λ = \frac{n−1}{2}. Once again, taking the sum over all possible values of λ and multiplying by 2, except when λ = \frac{n−1}{2}, we get the number of α-labeled graphs of odd size n. Thus, we have given a different and more intuitive proof to Sheppard’s result [10].

In Figure 3 we show the facts about cells per diagonal, where n = 7 and λ = 2.

Figure 3: Triangular atrrangements for n = 7 and λ = 2

Proposition 1. The number of α-labeled graphs of size n is

2 ∑_{λ=0}^{\frac{n−2}{2}}(λ!)^{2}(λ + 1)^{n−2λ}

when n is even, and

2 ∑_{λ=0}^{\frac{n−3}{2}}(λ!)^{2}(λ + 1)^{n−2λ} + (\frac{n − 1}{2})! (\frac{n + 1}{2})!

when n is odd.

In Table 1, we show the number of α-labeled graphs of size n for the first values of n. This is the sequence \underline{A005193} in Sloane’s Online Encyclopedia of Integer Sequences [12].

2.1 Enumerating Other Types of Labeled Graphs

Triangular arrangements can be also used to count other types of labeled graphs. Suppose G is a graph of size n. Let f : V (G) → L be a labeling of the vertices of G such that the weight of each edge uv of G is now defined as (f(u) + f(v)) (mod z).

\begin{matrix}n & α(n) & n & α(n) \\ 1 & 1 & 8 & 1930 \\ 2 & 2 & 9 & 9690 \\ 3 & 4 & 10 & 53578 \\ 4 & 10 & 11 & 322650 \\ 5 & 30 & 12 & 2106250 \\ 6 & 106 & 13 & 14790810 \\ 7 & 426 & 14 & 111327178 \end{matrix}

Table 1: Number of α-labeled graphs of size n

(a) f is harmonious when L = {0, 1, …, n − 1}, z = n, and

W_{f} = {0, 1, …, n − 1}. (See [6].)

(b) f is felicitous when L = {0, 1, …, n}, z = n, and

W_{f} = {0, 1, …, n − 1}. (See [4, 8].)

(c) f is elegant when L = {0, 1, …, n}, z = n + 1, and

W_{f} = {0, 1, …, n}. (See [2].)

Even when the nature of the weights is different now, all these labelings can be analyzed using these triangular arrangements. Now, the cell a_{ij} corresponds to (i + j) (mod z). We focus our attention on the harmonious labelings.

The definition of harmonious labelings can be extended to include graphs as trees, i.e., graphs of size n and order n + 1, by allowing the repetition of one label on two vertices. As a consequence of this repetition, the enumeration technique presented below gives the exact number of harmoniously labeled graphs of size n and order at most n; and a lower bound for the number of harmoniously labeled graphs of size n.

Because we want to determine h(n), that is, the number of harmoniously labeled graphs of size n and order at most n, we have n ≥ 3.

The weight w = n − 1 appears exactly once in each of the diagonals d_{k} where k is odd. Thus, when n is odd, w = n − 1 appears \frac{n−1}{2} times and \frac{n}{2} when n is even.

For every 0 ≤ w ≤ ⌊\frac{n−2}{2}⌋, both weights, w and n − 2 − w, appear in the diagonals d_{k} for every k ∈ A = {w + 2, w + 4, …, n − x} and every k ∈ B = {n − w, n − w + 2, …, n − y} where

x = \begin{cases}1, & if n is odd and w is even; \\ 2, & if n is odd and w is odd; \\ 2, & if n is even and w is even; \\ 1, & if n is even and w is odd. \end{cases}

and

y = \begin{cases}1, & if w is even; \\ 2, & if w is odd. \end{cases}

regardless the parity of n.

Notice that B = ∅ when w = 0 and w = n − 2. When n is even, |A| = \frac{n−x−w}{2} and |B| = \frac{w+2−x}{2} because x = y. Then the weight w

appears in \frac{n}{2} + 1 − x diagonals, that is, \frac{n}{2} − 1 times when it is even, and \frac{n}{2} times when it is odd. Therefore, the number of harmoniously labeled graphs of even size n, h(n), is given by

h(n) = (\frac{n}{2} − 1)^{\frac{n}{2}} (\frac{n}{2})^{\frac{n}{2}} .

When n is odd, |A| = \frac{n−x−w}{2} and |B| = \frac{w+2−y}{2}. Then the weight w appears in \frac{n+2−x−y}{2} diagonals, that is, \frac{n−1}{2} times. Hence,

h(n) = (\frac{n − 1}{2})^{n} .

Thus, we have proved the following proposition.

Proposition 2. The number of harmoniously labeled graphs of size n and order at most n is equal to:

• (\frac{n−1}{2})^{n} when n ≥ 3 is odd,

• (\frac{n}{2} − 1)^{\frac{n}{2}} (\frac{n}{2})^{\frac{n}{2}} when n ≥ 4 is even.

Using similar arguments we determined the number of felicitously and elegantly labeled graphs of size n.

Proposition 3. The number of felicitously labeled graphs of size n is

• (\frac{n+1}{2})^{n} when n is odd,

• (\frac{n}{2})^{\frac{n}{2}} (\frac{n+2}{2})^{\frac{n}{2}} when n is even.

Proposition 4. The number of elegantly labeled graphs of size n is

• (\frac{n−1}{2})^{\frac{n−1}{2}} (\frac{n+1}{2})^{\frac{n+1}{2}} when n is odd,

• (\frac{n}{2})^{n} when n is even.

3 The Number of Graceful Graphs

Let 𝒢_{m,n} be the family of all β-labeled graphs of order m and size n. We want to determine its cardinality. To do this, we use graceful triangles.

Recall that every graph G in 𝒢_{m,n} must have the integers 0 and n as labels. Since m ≤ n + 1, the remaining m − 2 labels of G form a subset of {1, 2, …, n − 1}. Thus, any β-labeling of G does not assign t = n + 1 − m integers from {1, 2, …, n − 1} as labels of G. Let A = {x_{1}, x_{2}, …, x_{t}} be the set formed by these numbers, where x_{i} < x_{i+1} for every 1 ≤ i ≤ t − 1.

Let d(j, x_{i}) denote the number of deleted (or forbidden) cells on the diagonal d_{j} of the graceful triangle when x_{i} is not a label of G. Suppose t = 1; we can see that:

• For 1 ≤ x_{1} ≤ ⌊\frac{n}{2}⌋

d(j, x_{1}) = \begin{cases}0, & if 1 ≤ j ≤ x_{1}; \\ 1, & if x_{1} + 1 ≤ j ≤ n − x_{1}; \\ 2, & if n − x_{1} + 1 ≤ j ≤ n. \end{cases}

• For ⌈\frac{n+1}{2}⌉ ≤ x_{1} ≤ n − 1

d(j, x_{1}) = \begin{cases}0, & if 1 ≤ j ≤ n − x_{1}; \\ 1, & if n − x_{1} + 1 ≤ j ≤ x_{1}; \\ 2, & if x_{1} + 1 ≤ j ≤ n. \end{cases}

In Figure 4 we show an example for n = 10, where x_{1} = 4. All the cells in the first 4 diagonals are available, all the cells except 1 can be used in the diagonals d_{5} and d_{6}, while in the remaining diagonals two cells cannot be used in each of them.

Figure 4: Counting of deleted cells

Thus, j − d(j, x_{1}) is the number of cells in d_{j} where a dot can be placed. Therefore, using the product rule, the number g(n, x_{1}) of β-labeled graphs of size n that do not have the integer x_{1} as a label is given by

g(n, x_{1}) = ∏_{j=1}^{n}(j − d(j, x_{1}))

In Table 2 we show the number g(n, i) of β-labeled graphs of size n ≥ 2 that do not use the integer i ∈ \{1, 2, …, n − 1\} as a label. This is the sequence \underline{A241094} in Sloane’s Online Encyclopedia of Integer Sequences [12].

n\i 1  2  3  4  5  6  7
2 0
3 1  1
4 4 4 4
5 18 24 24 18
6 96 144 144 144 96
7 600 960 1080 1080 960 600
8 4320 7200 8640 8640 8640 7200 4320

Table 2: β-labeled graphs where i is not a label

Suppose now that the integers x_{1} and x_{2} are not labels of G. The number of available cells on d_{j} is

j − d(j, x_{1}) − d(j, x_{2}),

except when j = n + 1 − (x_{2} − x_{1}), where this number is

j − d(j, x_{1}) − d(j, x_{2}) + 1,

because the cell a_{x_{1}x_{2}} was eliminated twice (see Figure 5a). Then the number g(n, x_{1}, x_{2}) of β-labeled graphs of size n that do not have the integers x_{1} and x_{2} as labels, is given by

g(n, x_{1}, x_{2}) = ∏_{j=1}^{n}(j − d(j, x_{1}) − d(j, x_{2}) + δ_{x_{1}x_{2}}),

where

δ_{x_{1}x_{2}} = \begin{cases}1, & if j = n + 1 − (x_{2} − x_{1}); \\ 0, & otherwise. \end{cases}

Now that a pattern has been established, we proceed to find the general formula that allows us to count the number of β-labeled graphs of size n that do not have as labels, t numbers from {1, 2, …, n − 1}.

Figure 5: Overcounting of deleted cells

Notice that when t numbers from {1, 2, …, n − 1} are not used, the number of cells, in the triangular arrangement, that have been eliminated twice is given by \frac{t(t−1)}{2} (see Figure 4). Thus,

δ = ∑_{∀x_{i},x_{j}∈A} δ_{x_{i}x_{j}},

and the number of β-labeled graphs of size n that do not have, as labels, the integers in A = {x_{1}, x_{2}, …, x_{t}} is given by

g(n, A) = ∏_{j=1}^{n} (j − ∑_{i=1}^{t} d(j; x_{i}) + δ) .

Therefore, the number g(n, t) of β-labeled graphs of size n that do not use t numbers from {1, 2, …, n − 1} as labels, is obtained by adding the numbers g(n, A) for all possible t-element subsets A of {1, 2, …, n − 1}, that is,

g(n, t) = ∑_{A⊆{1,2,...,n−1}} g(n, A)

= ∑_{A⊆{1,2,...,n−1}} (∏_{j=1}^{n} (j − ∑_{i=1}^{t} d(j, x_{i}) + δ))

In the next theorem we use the principle of inclusion and exclusion and the numbers g(n, t) to count the number of β-labeled graphs of size n and order n + 1. Notice that these kind of graphs include all β-labeled trees.

Theorem 5. The number of graceful graphs of order n + 1 and size n is given by

g(n, 0) = n! + ∑_{k=1}^{n−1}(−1)^{k}g(n, k).

Proof. Let g(n, 0) represent the number of β-labeled graphs of size n and order n + 1. For any 1 ≤ k < n − 1, the number g(n, t) includes the number g(n, t + 1). Since there are n! graceful-graphs of size n and the numbers g(n, k) satisfy the conditions of the principle of inclusion and exclusion, we have proven our result.

The first values of g(n, 0) can be seen in the lower diagonal of Table 3. For example, 7008 is the number of β-labeled graphs of size 8 and order 9. We can also use g(n, 0) as an upper bound for the number of β-labeled trees of size n.

Now we can focus on our final goal, that is, to know the value of |𝒢_{m,n}|. Since g(n, t) counts the number of β-labeled graphs of size n that do not use the t numbers in A = {x_{1}, x_{2}, …, x_{t}} as labels, g(n, t) includes g(n, t + 1). Suppose that k is the largest integer in {1, 2, …, n − 1} such that g(n, k) ≠ 0. Then

|𝒢_{n+1−k,n}| = g(n, k).

Let \overline{g}(n, t) denote the number of β-labeled graphs of size n that do not use exactly t numbers from \{1, 2, …, n − 1\} as labels. Thus \overline{g}(n, k) = g(n, k). Moreover, to determine \overline{g}(n, k − 1) we need to eliminate from g(n, k − 1) all those labeled graphs counted by \overline{g}(n, k). Since every set with k elements contains \binom{k}{k−1} = k subsets of cardinality k − 1, we know that \overline{g}(n, k − 1) = g(n, k − 1) − k\overline{g}(n, k). This equation is used within the proof of our main result.

Theorem 6. The number \overline{g}(n, t) of β-labeled graphs of size n and order m = n + 1 − t is given by

\overline{g}(n, t) = g(n, t) − ∑_{i=1}^{k−t} \binom{t + i}{t}\overline{g}(n, t + i)

where k is the largest integer in \{1, 2, …, n − 1\} such that \overline{g}(n, k) ≠ 0.

Proof. Suppose that the value of \overline{g}(n, t + i) is known for every 1 ≤ i ≤ k − t. Thus

\binom{t + i}{t}\overline{g}(n, t + i)

counts the number of times a β-labeled graph of size n and order n + 1 − t − i has been counted inside g(n, t). Since 1 ≤ i ≤ k,

\overline{g}(n, t) = g(n, t) − ∑_{i=1}^{k−t} \binom{t + i}{t}\overline{g}(n, t + i).

This concludes the proof.

Observe that this last formula can be written in terms of g(n, t + i) instead of \overline{g}(n, t + i). Doing back substitution we arrive to the following equivalent formula.

Theorem 7. The number \overline{g}(n, t) of β-labeled graphs of size n and order n + 1 − t is given by

\overline{g}(n, t) = g(n, t) + ∑_{i=1}^{k−t}(−1)^{i}\binom{t + i}{t}g(n, t + i).

In Table 3 we show |𝒢_{m,n}| for the first values of n and m.

m\n 1 2 3 4 5 6 7  8  9  10
2  1
3  2 2
4  4 12 8 2
5 12 68 106 88 32 8
6  44 406 1186 1728 1696 964
7  206 2644 12096 29536 45496
8  1122 19456 126304 448512
9  7008 155960 1365992
10  49376 1380476
11  387360

Table 3: First values of |𝒢_{m,n}|

4 Conclusions

Triangular arrangements have shown to be extremely useful to count the number of β-labeled graphs of size n and order m. Now, that these numbers have been determined, we can use them for further investigations of this type of labeled graphs. In particular, we can take the subfamily of size n and order n + 1 and study how many of them correspond to connected graphs, that is, trees. If this is possible, we would have more information toward the proof of the graceful tree conjecture.

5 Note

During the preperation of the final version of this paper we became aware of the work of Whitty [13]. In this paper, Whitty determined the number of β-labeled trees of order n to be the leading coefficient of the rook polymonial associated with the Klein bottle.

6 Acknowledgments

We would like to extend our sincere thanks to the referees of this paper for their extremely helpful comments and the high quality of their work that helped us improve the accuracy of this paper.

References

[1] C. Barrientos, Difference Vertex Labelings, Ph.D. Thesis, Universitat Politécnica de Catalunya, Barcelona, 2004.

[2] G. J. Chang, D. F. Hsu, and D. G. Rogers, Additive variations on a graceful theme: some results on harmonious and other related graphs, in Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I, Congr. Numer. 32 (1981), 181–197.

[3] G. Chartrand and L. Lesniak, Graphs & Digraphs, 2nd edition, Wadsworth & Brooks/Cole Advanced Books & Software, 1986.

[4] J. A. Gallian, A dynamic survey of graph labeling, Elect. J. Combin., DS6 (2013).

[5] S. W. Golomb, How to number a graph, in R. C. Read, ed., Graph Theory and Computing, Academic Press, 1972, pp. 23–37.

[6] R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graphs, SIAM J. Algebraic Discrete Methods, 1 (1980) 382–404.

[7] M. Haviar and M. Ivaška, Vertex labelings of simple graphs, submitted, 2014.

[8] S. M. Lee, E. Schmeichel, and S. C. Shee, On felicitous graphs, Discrete Math., 93 (1991) 201–209.

[9] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symp., Rome, July 1966), Gordon and Breach, 1967, pp. 349–355.

[10] D. Sheppard, The factorial representation of major balanced graphs, Discrete Math., 15 (1976) 379–388.

[11] C.-L. Shiue and H.-C. Lu, Trees which admit no α-labeling, Ars. Combin., 103 (2012) 453–463.

[12] N. J. A. Sloane, The on-line encyclopedia of integer sequences, 2014, http://oeis.org.

[13] R. W. Whitty, Rook polynomials on 2-dimensional surfaces and graceful labellings of graphs, Discrete Math., 308 (2008) 674–683.

[14] C. Zhi-Zeng, A generalization of the Bodendiek conjecture about graceful graphs, in R. Bodendiek and R. Henn, eds., Topics in Combinatorics and Graph Theory, Essays in Honour of Gerhard Ringel, Physica-Verlag Heidelberg, 1990, pp. 737–746.

2010 Mathematics Subject Classification: Primary 05C30; Secondary 05C78. Keywords: graceful graph, α-graph, enumeration, graceful triangle.

(Concerned with sequences \underline{A005193}, \underline{A241094}.)

Received July 22 2014; revised versions received November 16 2014; December 5 2014. Published in Journal of Integer Sequences, January 12 2015.

Return to Journal of Integer Sequences home page.