\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{enumitem}
\usepackage[mathscr]{euscript}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Enumerating Families of Labeled Graphs
}
\vskip 1cm
\large
Christian Barrientos and Sarah Minion\\
Department of Mathematics\\
Clayton State University\\
Morrow, GA 30260 \\
USA\\
\href{mailto:sarah.m.minion@gmail.com}{\tt sarah.m.minion@gmail.com} \\
\href{mailto:chr_barrientos@yahoo.com}{\tt chr\_barrientos@yahoo.com}
\end{center}
\vskip .2 in
\begin{abstract}
In 1966, Rosa introduced, among others, $\alpha$- and $\beta$-labelings
as tools to solve the isomorphic decomposition problem of the complete
graph. Ten years later, Sheppard calculated the number of $\alpha$- and
$\beta$-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.
\end{abstract}
\section{Introduction}
\label{sec:introduction}
By a {\it graph\/} we mean a finite undirected graph with no loops or multiple edges (for all undefined graph-theoretical terminology see \cite{3,4}). In addition, graphs considered here have no isolated vertices. By a \emph{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 $\vert f(v_i) - f(v_j) \vert$ where $v_iv_j$ is an edge of $G$.
Now consider a labeling $f$ of a graph $G$ of size $n$ and the following conditions:
\begin{enumerate}[label=(\alph*)]
\item $L_f \subseteq \{ 0,1,\dots,n \}$;
\item $W_f = \{ 1,2,\dots,n \}$;
\item there exists $\lambda$, $\lambda \in \{ 0,1,\dots,n \}$, such that for any edge $v_iv_j$ of the graph $G$, either $f(v_i) \leq \lambda < f(v_j)$ or $f(v_j) \leq \lambda < f(v_i)$ holds.
\end{enumerate}
A labeling satisfying the conditions (a) and (b) is called a \emph{$\beta$-labeling} (or \emph{graceful} labeling). If in addition the condition (c) is satisfied, we have an \emph{$\alpha$-labeling}.
For every $v \in V(G)$, the number $f(v)$ is called the \emph{label} of $v$; for every $uv \in E(G)$, the number $\vert f(u) - f(v) \vert$ is called the \emph{weight} of $uv$. When $f$ is a $\beta$-labeling we say that $G$ is \emph{graceful} or it is \emph{$\beta$-labeled}; if $f$ is an $\alpha$-labeling we say that $G$ is an \emph{$\alpha$-graph} or it is \emph{$\alpha$-labeled}. The number $\lambda$ in (c) is called the \emph{boundary value} of $f$.
These labelings have been intensively studied since their introduction by Rosa \cite{9} in the mid-sixties. Rosa called them $\beta$- and $\alpha$-valuations, respectively. The term graceful labeling was introduced by Golomb \cite{5} years later to refer to Rosa's $\beta$-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 \cite{4}.
Let $G$ be a graph of order $m$ and size $n$. It is well-known that if $G$ is graceful, then $m - n \leq 1$. Also, if $G$ is an $\alpha$-graph, then $G$ is bipartite. Suppose that $f$ is a $\beta$-labeling of $G$, then its complementary labeling $\overline{f}$, defined by $\overline{f}(v) = n - f(v)$, for every $v \in V(G)$, is also a $\beta$-labeling. This fact can be used to prove that the number of different $\beta$-labelings of $G$ is even, except when $G \cong K_2$.
When $f$ is an $\alpha$-labeling of $G$ with boundary value $\lambda$, the $\alpha$-labeling $f^{-1}$ of $G$ given by,
\begin{align*}
f^{-1}(v) = \lambda - f(v)~ (\textup{mod } n + 1),
\end{align*}
is called the \emph{inverse} labeling of $f$. Thus, depending on the symmetry of the structure of $G$, the number of different $\alpha$-labelings of $G$ is a multiple of $4$.
In 1976, Sheppard \cite{10} counted the number of different $\alpha$- and $\beta$-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 $\beta$-labeled graphs of size $n$ is $n!$. He also counted the number of $\alpha$-labeled graphs of size $n$ to be
\begin{align*}
2\sum_{\lambda = 0}^{\frac{n - 2}{2}} (\lambda!)^2 (\lambda + 1)^{n - 2 \lambda}
\end{align*}
when $n$ is even, and
\begin{align*}
2\sum_{\lambda = 0}^{\frac{n - 3}{2}} (\lambda!)^2 (\lambda + 1)^{n - 2 \lambda} + \left( \frac{n - 1}{2} \right)! \left( \frac{n + 1}{2} \right)!
\end{align*}
when $n$ is odd.
In Section \ref{sec:gracefultriangles} 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 \ref{sec:thenumber} we determine the exact number of gracefully labeled graphs of size $n$ and order $m$.
\section{Graceful Triangles}
\label{sec:gracefultriangles}
Let $f$ be a $\beta$-labeling of a graph $G$ of order $m$ and size $n$. The $\beta$-labeled graph $G$ can be described by means of matrices. One such matrix is the \emph{graceful matrix} $A(G) = [ a_{ij} ]$, where $a_{ij} = 1$ if there exists $uv \in E(G)$ such that $f(u) = i$ and $f(v) = j$, and $a_{ij} = 0$ otherwise, for $0 \leq i,j \leq n$. These matrices were introduced by Zhi-Zeng \cite{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 $\beta$-labeled graph $G$ can be seen in the triangular arrangement formed by the cells $a_{ij}$ of $A(G)$ where $i < j$, $0 \leq i \leq n - 1$, and $1 \leq j \leq n$. We call this arragement the \emph{graceful triangle}. In Figure \ref{fig1} we show a $\beta$-labeled graph of order $6$ and size $10$ together with its graceful triangle, where the adjacencies have been represented by dots.
\begin{figure}[h]
\begin{center}
\includegraphics[scale=.20]{1}
\end{center}
\caption{Graceful Triangle}
\label{fig1}
\end{figure}
The graceful matrix tool has been used by other authors. Barrientos \cite{1}, Zhi-Zeng \cite{14}, and Shiue and Lu \cite{11}, use it to prove the existence of $\alpha$- and $\beta$-labelings for certain families of graphs. In addition, Haviar and Iva\v{s}ka \cite{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 $\beta$-labeled graph $G$ of order $m$ and size $n$, its graceful triangle contains $n$ diagonals $d_1,d_2,\dots,d_n$, where $d_k$ is formed by the cells $a_{ij}$ where $j - i = n + 1 - k$, $1 \leq k \leq 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 $\beta$-labeled graph of size $n$. Thus, we can use them to count the number of $\beta$-labeled graphs with $n$ edges.
Let $d_1,d_2,\dots,d_n$ be the diagonals of a triangular arrangement. Since for every $1 \leq k \leq 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!$ $\beta$-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 $\alpha$-labeling $f$, with boundary value $\lambda$, is represented in a triangular arrangement, all the adjacencies lie in a rectangle with corners $a_{0n}, a_{0(\lambda + 1)} a_{\lambda(\lambda + 1)},a_{\lambda n}$. We refer to this rectangle as the \emph{rectangle determined by $\lambda$}. An example of this fact is shown in Figure \ref{fig2} for an $\alpha$-graph of size $7$ and boundary value $3$.
\begin{figure}[h]
\begin{center}
\includegraphics[scale=.20]{2}
\end{center}
\caption{Triangular representation of an $\alpha$-labeling}
\label{fig2}
\end{figure}
Notice that the inverse labeling of $f$ is obtained rotating this rectangle by $180$ degrees.
This representation of $\alpha$-labelings is extremely useful to count the number of $\alpha$-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 $\lambda$ and multiply by $2$. When $n$ is even, the rectangle determined by $\lambda$ for $0 \leq \lambda \leq \frac{n-2}{2}$, is symmetric to the one determined by $n - \lambda - 1$.
Let $f$ be an $\alpha$-labeling of $G$ with boundary value $\lambda$, where $0 \leq \lambda \leq \frac{n-2}{2}$. For $k \in \{ 1,2,\dots, \lambda \}$, the diagonals $d_k$ and $d_{n + 1 - k}$ have $k$ cells that can be used to place a dot; thus there are $(\lambda !)^2$ possible distributions of the dots. For $k \in \{ \lambda + 1, \lambda + 2, \dots, n - \lambda \}$, the diagonals $d_k$ have $\lambda + 1$ cells where a dot can be placed, thus there are $(\lambda + 1)^{n - 2 \lambda}$ possible distributions of the dots. Hence, there are $(\lambda !)^2 (\lambda + 1)^{n - 2 \lambda}$ graphs of even size $n$ that admit an $\alpha$-labeling with boundary value $\lambda$. Taking the sum over all possible values of $\lambda$ and multiplying by $2$, we obtain the number of $\alpha$-labeled graphs of even size $n$.
When $n$ is odd, the rectangle determined by $\lambda$ for $0 \leq \lambda \leq \frac{n - 3}{2}$, is symmetric to the one determined by $n - \lambda - 1$. The only difference with the even case is when $\lambda = \frac{n - 1}{2}$. In this case the diagonals $d_k$ and $d_{n + 1 - k}$, for $1 \leq k \leq \lambda$, have $k$ cells that can be used to place a dot, i.e., there are $\left( \frac{n - 1}{2} ! \right)^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
\begin{align*}
\left( \left( \frac{n - 1}{2} \right) ! \right)^2 \frac{n + 1}{2} = \left( \frac{n - 1}{2}\right) ! \left(\frac{n + 1}{2}\right)!,
\end{align*}
we have that there are $(\lambda !)^2 (\lambda + 1)^{n - 2 \lambda}$ graphs of size $n$ that admit an $\alpha$-labeing with boundary value $\lambda$, $0 \leq \lambda \leq \frac{n - 3}{2}$ and $\left( \frac{n - 1}{2} \right) ! \left( \frac{n + 1}{2} \right) !$ with boundary value $\lambda = \frac{n - 1}{2}$. Once again, taking the sum over all possible values of $\lambda$ and multiplying by $2$, except when $\lambda = \frac{n - 1}{2}$, we get the number of $\alpha$-labeled graphs of odd size $n$. Thus, we have given a different and more intuitive proof to Sheppard's result \cite{10}.
In Figure \ref{fig3} we show the facts about cells per diagonal, where $n = 7$ and $\lambda = 2$.
\begin{figure}[h]
\begin{center}
\includegraphics[scale=.15]{3}
\end{center}
\caption{Triangular atrrangements for $n = 7$ and $\lambda = 2$}
\label{fig3}
\end{figure}
\begin{proposition}
The number of $\alpha$-labeled graphs of size $n$ is
\begin{align*}
2 \sum_{\lambda = 0}^{\frac{n - 2}{2}} (\lambda !)^2 (\lambda + 1)^{n - 2 \lambda}
\end{align*}
when $n$ is even, and
\begin{align*}
2 \sum_{\lambda = 0}^{\frac{n - 3}{2}} (\lambda !)^2 (\lambda + 1)^{n - 2 \lambda} + \left( \frac{n - 1}{2} \right) ! \left( \frac{n + 1}{2} \right)!
\end{align*}
when $n$ is odd.
\label{prop1}
\end{proposition}
In Table \ref{tab1}, we show the number of $\alpha$-labeled graphs of size $n$ for the first values of $n$. This is the sequence
\seqnum{A005193} in Sloane's
{\it Online Encyclopedia of Integer Sequences} \cite{12}.
\begin{table}[h!]
\renewcommand\thetable{1}
\begin{center}
\begin{tabular}{ l l | l l }
$n$ & $\alpha(n)$ & $n$ & $\alpha(n)$\\\hline
$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{tabular}
\end{center}
\caption {Number of $\alpha$-labeled graphs of size $n$}
\label{tab1}
\end{table}
\subsection{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) \rightarrow 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)) ~(\textup{mod }z)$.
\begin{enumerate}[label=(\alph*)]
\item $f$ is \emph{harmonious} when $L = \{ 0,1,\dots, n - 1 \}$, $z = n$, and
$W_f = \{ 0,1,\dots, n - 1 \}$. (See \cite{6}.)
\item $f$ is \emph{felicitous} when $L = \{ 0,1,\dots, n \}$, $z = n$, and
$W_f = \{ 0,1,\dots, n - 1 \}$. (See \cite{4,8}.)
\item $f$ is \emph{elegant} when $L = \{ 0,1,\dots, n \}$, $z = n + 1$, and
$W_f = \{ 0,1,\dots, n \}$. (See \cite{2}.)
\end{enumerate}
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)~ (\textup{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 \geq 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 \leq w \leq \big\lfloor \frac{n - 2}{2} \big\rfloor$, both weights, $w$ and $n - 2 - w$, appear in the diagonals $d_k$ for every $k \in A = \{ w + 2, w + 4, \dots, n - x \}$ and every $k \in B = \{ n - w, n - w + 2, \dots, n - y \}$ where
$$
x =
\begin{cases}
1, & \text{if } n\text{ is odd and } w \text{ is even;} \\
2, & \text{if } n\text{ is odd and } w \text{ is odd;} \\
2, & \text{if } n\text{ is even and } w \text{ is even;} \\
1, & \text{if } n\text{ is even and } w \text{ is odd.} \\
\end{cases}
$$
\noindent and
$$
y =
\begin{cases}
1, & \text{if } w \text{ is even;} \\
2, & \text{if } w \text{ is odd.}
\end{cases}
$$
\noindent regardless the parity of $n$.
Notice that $B = \varnothing$ when $w=0$ and $w=n - 2$.
When $n$ is even, $\vert A \vert = \frac{n - x - w}{2}$ and $\vert B \vert = \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
\begin{align*}
h(n) = \left( \frac{n}{2} - 1 \right)^{\frac{n}{2}} \left( \frac{n}{2} \right)^{\frac{n}{2}}.
\end{align*}
When $n$ is odd, $\vert A \vert = \frac{n - x - w}{2}$ and $\vert B \vert = \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,
\begin{align*}
h(n) = \left( \frac{n - 1}{2}\right)^{n}.
\end{align*}
Thus, we have proved the following proposition.
\begin{proposition}
The number of harmoniously labeled graphs of size $n$ and order at most $n$ is equal to:
\begin{itemize}
\item $\left( \frac{n - 1}{2} \right)^{n}$ when $n \geq 3$ is odd,
\item $\left( \frac{n}{2} - 1 \right)^{\frac{n}{2}} \left( \frac{n}{2} \right)^{\frac{n}{2}}$ when $n \geq 4$ is even.
\end{itemize}
\label{prop2}
\end{proposition}
Using similar arguments we determined the number of felicitously and elegantly labeled graphs of size $n$.
\begin{proposition}
The number of felicitously labeled graphs of size $n$ is
\begin{itemize}
\item $\left( \frac{n + 1}{2} \right)^{n}$ when $n$ is odd,
\item $\left( \frac{n}{2} \right)^{\frac{n}{2}} \left( \frac{n + 2}{2} \right)^{\frac{n}{2}}$ when $n$ is even.
\end{itemize}
\label{prop3}
\end{proposition}
\begin{proposition}
The number of elegantly labeled graphs of size $n$ is
\begin{itemize}
\item $\left( \frac{n - 1}{2} \right)^{\frac{n - 1}{2}} \left( \frac{n +1}{2} \right)^{\frac{n + 1}{2}}$ when $n$ is odd,
\item $\left( \frac{n}{2} \right)^{n}$ when $n$ is even.
\end{itemize}
\label{prop4}
\end{proposition}
\section{The Number of Graceful Graphs}
\label{sec:thenumber}
Let $\mathscr{G}_{m,n}$ be the family of all $\beta$-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 $\mathscr{G}_{m,n}$ must have the integers 0 and $n$ as labels. Since $m \leq n + 1$, the remaining $m - 2$ labels of $G$ form a subset of $\{ 1,2,\dots,n - 1 \}$. Thus, any $\beta$-labeling of $G$ does not assign $t = n + 1 - m$ integers from $\{ 1,2,\dots,n - 1 \}$ as labels of $G$. Let $A = \{ x_1,x_2,\dots,x_t \}$ be the set formed by these numbers, where $x_i < x_{i + 1}$ for every $1 \leq i \leq 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:
\begin{itemize}
\item For $1 \leq x_1 \leq \lfloor \frac{n}{2} \rfloor$
$$
d(j,x_1) =
\begin{cases}
0, & \text{if } 1 \leq j \leq x_1; \\
1, & \text{if } x_1 + 1 \leq j \leq n - x_1; \\
2, & \text{if } n - x_1 + 1 \leq j \leq n.
\end{cases}
$$
\item For $\lceil \frac{n + 1}{2} \rceil \leq x_1 \leq n - 1$
$$
d(j,x_1) =
\begin{cases}
0, & \text{if } 1 \leq j \leq n - x_1; \\
1, & \text{if } n - x_1 + 1 \leq j \leq x_1; \\
2, & \text{if } x_1 + 1 \leq j \leq n.
\end{cases}
$$
\end{itemize}
In Figure \ref{fig4} 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.
\begin{figure}[h]
\begin{center}
\includegraphics[scale=.15]{4}
\end{center}
\caption{Counting of deleted cells}
\label{fig4}
\end{figure}
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 $\beta$-labeled graphs of size $n$ that do not have the integer $x_1$ as a label is given by
\begin{align*}
g(n,x_1) = \prod_{j = 1}^{n} (j - d(j,x_1))
\end{align*}
In Table \ref{tab2} we show the number $g(n,i)$ of $\beta$-labeled graphs of size $n \geq 2$ that do not use the integer $i \in \{ 1,2,\dots,n - 1 \}$ as a label. This is the sequence
\seqnum{A241094} in Sloane's
{\it Online Encyclopedia of Integer Sequences} \cite{12}.
\begin{table}[h!]
\renewcommand\thetable{2}
\begin{center}
\begin{tabular}{l | l l l l l l l}
$n \backslash i$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$\\\hline
$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$
\end{tabular}
\end{center}
\caption {$\beta$-labeled graphs where $i$ is not a label}
\label{tab2}
\end{table}
Suppose now that the integers $x_1$ and $x_2$ are not labels of $G$. The number of available cells on $d_j$ is
\begin{align*}
j - d(j,x_1) - d(j,x_2),
\end{align*}
except when $j = n + 1 - (x_2 - x_1)$, where this number is
\begin{align*}
j - d(j,x_1) - d(j,x_2) + 1,
\end{align*}
because the cell $a_{x_1x_2}$ was eliminated twice (see Figure \ref{fig5}a). Then the number $g(n,x_1,x_2)$ of $\beta$-labeled graphs of size $n$ that do not have the integers $x_1$ and $x_2$ as labels, is given by
\begin{align*}
g(n,x_1,x_2) = \prod_{j=1}^{n} (j - d(j,x_1) - d(j,x_2) + \delta_{x_1x_2}),
\end{align*}
where
$$
\delta_{x_1x_2} =
\begin{cases}
1, & \text{if } j = n + 1 - (x_2 - x_1); \\
0, & \text{otherwise}.
\end{cases}
$$
\begin{figure}[h]
\begin{center}
\includegraphics[scale=.25]{5}
\end{center}
\caption{Overcounting of deleted cells}
\label{fig5}
\end{figure}
Now that a pattern has been established, we proceed to find the general formula that allows us to count the number of $\beta$-labeled graphs of size $n$ that do not have as labels, $t$ numbers from $\{ 1,2, \dots,n - 1 \}$.
Notice that when $t$ numbers from $\{ 1,2,\dots, 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 \ref{fig4}). Thus,
\begin{align*}
\delta = \sum_{\forall x_i,x_j \in A} \delta_{x_ix_j},
\end{align*}
and the number of $\beta$-labeled graphs of size $n$ that do not have, as labels, the integers in $A = \{ x_1,x_2,\dots,x_t \}$ is given by
\begin{align*}
g(n,A) = \prod_{j=1}^{n} \left( j - \sum_{i=1}^{t} d(j;x_i) + \delta \right).
\end{align*}
Therefore, the number $g(n,t)$ of $\beta$-labeled graphs of size $n$ that do not use $t$ numbers from $\{ 1,2,\dots,n - 1 \}$ as labels, is obtained by adding the numbers $g(n,A)$ for all possible $t$-element subsets $A$ of $\{ 1,2,\dots,n - 1 \}$, that is,
\begin{align*}
g(n,t) &= \sum_{A \subseteq \{ 1,2,\dots,n - 1 \}} g(n,A)\\
&= \sum_{A \subseteq \{ 1,2,\dots,n - 1 \}} \left( \prod_{j=1}^{n} \left( j - \sum_{i=1}^{t} d(j,x_i) + \delta \right) \right)
\end{align*}
In the next theorem we use the principle of inclusion and exclusion and the numbers $g(n,t)$ to count the number of $\beta$-labeled graphs of size $n$ and order $n + 1$. Notice that these kind of graphs include all $\beta$-labeled trees.
\begin{theorem}
The number of graceful graphs of order $n + 1$ and size $n$ is given by
\begin{align*}
g(n,0) = n! + \sum_{k = 1}^{n - 1} (-1)^k g(n,k).
\end{align*}
\label{thm5}
\end{theorem}
\begin{proof}
Let $g(n,0)$ represent the number of $\beta$-labeled graphs of size $n$ and order $n + 1$. For any $1 \leq 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.
\end{proof}
The first values of $g(n,0)$ can be seen in the lower diagonal of Table \ref{tab3}. For example, 7008 is the number of $\beta$-labeled graphs of size 8 and order 9. We can also use $g(n,0)$ as an upper bound for the number of $\beta$-labeled trees of size $n$.
Now we can focus on our final goal, that is, to know the value of $\vert \mathscr{G}_{m,n} \vert$. Since $g(n,t)$ counts the number of $\beta$-labeled graphs of size $n$ that do not use the $t$ numbers in $A = \{ x_1,x_2,\dots,x_t \}$ as labels, $g(n,t)$ includes $g(n,t + 1)$. Suppose that $k$ is the largest integer in $\{ 1,2,\dots,n - 1 \}$ such that $g(n,k) \not= 0$. Then
\begin{align*}
\vert \mathscr{G}_{n + 1 - k,n} \vert = g(n,k).
\end{align*}
Let $\overline{g}(n,t)$ denote the number of $\beta$-labeled graphs of size $n$ that do not use exactly $t$ numbers from $\{ 1,2,\dots,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.
\begin{theorem}
The number $\overline{g}(n,t)$ of $\beta$-labeled graphs of size $n$ and order $m = n + 1 - t$ is given by
\begin{align*}
\overline{g}(n,t) = g(n,t) - \sum_{i = 1}^{k - t} \binom{t + i}{t} \overline{g}(n,t + i)
\end{align*}
where $k$ is the largest integer in $\{ 1,2,\dots,n - 1 \}$ such that $\overline{g}(n,k) \not= 0$.
\label{thm6}
\end{theorem}
\begin{proof}
Suppose that the value of $\overline{g}(n,t + i)$ is known for every $1 \leq i \leq k - t$. Thus
\begin{align*}
\binom{t + i}{t} \overline{g}(n,t + i)
\end{align*}
counts the number of times a $\beta$-labeled graph of size $n$ and order $n + 1 - t - i$ has been counted inside $g(n,t)$. Since $1 \leq i \leq k$,
\begin{align*}
\overline{g}(n,t) = g(n,t) - \sum_{i = 1}^{k - t} \binom{t + i}{t} \overline{g}(n,t + i).
\end{align*}
This concludes the proof.
\end{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.
\begin{theorem}
The number $\overline{g}(n,t)$ of $\beta$-labeled graphs of size $n$ and order $n + 1 - t$ is given by
\begin{align*}
\overline{g}(n,t) = g(n,t) + \sum_{i = 1}^{k - t} (-1)^i \binom{t + i}{t} g(n,t + i).
\end{align*}
\label{thm7}
\end{theorem}
In Table \ref{tab3} we show $\vert \mathscr{G}_{m,n} \vert$ for the first values of $n$ and $m$.
\begin{table}[h!]
\renewcommand\thetable{3}
\begin{center}
\begin{tabular}{l | l l l l l l l l l l}
$m \backslash n$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$\\\hline
$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$
\end{tabular}
\end{center}
\caption {First values of $\vert \mathscr{G}_{m,n} \vert$}
\label{tab3}
\end{table}
\section{Conclusions}
\label{sec:conclusions}
Triangular arrangements have shown to be extremely useful to count the number of $\beta$-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.
\section{Note}
\label{sec:note}
During the preperation of the final version of this paper we became aware of the work of Whitty \cite{13}. In this paper, Whitty determined the number of $\beta$-labeled trees of order $n$ to be the leading coefficient of the rook polymonial associated with the Klein bottle.
\section{Acknowledgments}
\label{sec:ack}
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.
\begin{thebibliography}{99}
\bibitem{1} C. Barrientos, Difference Vertex Labelings, Ph.D. Thesis,
Universitat Polit\'ecnica de Catalunya, Barcelona, 2004.
\bibitem{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 \emph{Proceedings of the Twelfth Southeastern
Conference on Combinatorics, Graph Theory and Computing, Vol.~I},
{\it Congr. Numer.} {\bf 32} (1981), 181--197.
\bibitem{3} G. Chartrand and L. Lesniak, \emph{Graphs \& Digraphs},
2nd edition, Wadsworth \& Brooks/Cole Advanced Books \& Software, 1986.
\bibitem{4} J. A. Gallian, A dynamic survey of graph labeling,
\emph{Elect. J. Combin.}, DS6 (2013).
\bibitem{5} S. W. Golomb, How to number a graph, in R. C. Read,
ed., \emph{Graph Theory
and Computing}, Academic Press, 1972, pp.~23--37.
\bibitem{6} R. L. Graham and N. J. A. Sloane, On additive bases and
harmonious graphs, \emph{SIAM J. Algebraic Discrete Methods},
\textbf{1} (1980) 382--404.
\bibitem{7} M. Haviar and M. Iva\v{s}ka, Vertex labelings of simple
graphs, submitted, 2014.
\bibitem{8} S. M. Lee, E. Schmeichel, and S. C. Shee, On felicitous
graphs, \emph{Discrete Math.}, \textbf{93} (1991) 201--209.
\bibitem{9} A. Rosa, On certain valuations of the vertices of a graph,
\emph{Theory of Graphs (Internat. Symp., Rome, July 1966)}, Gordon and
Breach, 1967, pp.~349--355.
\bibitem{10} D. Sheppard, The factorial representation of major
balanced graphs, \emph{Discrete Math.}, \textbf{15} (1976) 379--388.
\bibitem{11} C.-L. Shiue and H.-C. Lu, Trees which admit no
$\alpha$-labeling, \emph{Ars. Combin.}, \textbf{103} (2012) 453--463.
\bibitem{12} N. J. A. Sloane, The on-line encyclopedia of integer
sequences, 2014, \url{http://oeis.org}.
\bibitem{13} R. W. Whitty, Rook polynomials on $2$-dimensional surfaces
and graceful labellings of graphs, \emph{Discrete Math.},
\textbf{308} (2008) 674--683.
\bibitem{14} C. Zhi-Zeng, A generalization of the Bodendiek conjecture
about graceful graphs, in R. Bodendiek and R. Henn, eds.,
\emph{Topics in Combinatorics and Graph
Theory, Essays in Honour of Gerhard Ringel},
Physica-Verlag Heidelberg, 1990, pp.~737--746.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05C30; Secondary 05C78.
\noindent \emph{Keywords: }
graceful graph, $\alpha$-graph, enumeration, graceful triangle.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A005193},
\seqnum{A241094}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received July 22 2014;
revised versions received November 16 2014; December 5 2014.
Published in {\it Journal of Integer Sequences}, January 12 2015.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}