\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}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
%\newenvironment{proof}{\begin{trivlist}\item{\bf{Proof.}}}
%{\hfill$\Box$\end{trivlist}}
\begin{center}
\vskip 1cm{\LARGE\bf On the Number of Labeled $k$-arch Graphs }
\vskip 1cm \large
Saverio Caminiti and Emanuele G. Fusco\\
Department of Computer Science\\
University of Rome ``La Sapienza''\\
Via Salaria 113\\
00198 Rome\\
Italy\\
\href{mailto:caminiti@di.uniroma1.it}{\tt caminiti@di.uniroma1.it}\\
\href{mailto:fusco@di.uniroma1.it}{\tt fusco@di.uniroma1.it}\\
\end{center}
\vskip .2 in
\begin{abstract}
In this paper we deal with $k$-arch graphs, a superclass of trees
and $k$-trees. We give a recursive function counting the number of
labeled $k$-arch graphs. Our result relies on a generalization of
the well-known Pr\"ufer code for labeled trees. In order to
guarantee the generalized code to be a bijection, we characterize
the valid code strings.
A previous attempt at counting the number of labeled $k$-arch graphs
was made by Lamathe. We point out an error in his work, and
prove it by giving a counterexample.
\end{abstract}
\section{Introduction}
The problem of counting labeled trees has been widely studied, and
there exists a variety of proofs for the well-known Cayley
formula \cite{C89}, which states that the number of labeled trees of
$n$ nodes is $n^{n-2}$ (for a survey, see \cite{M67}). Among
these proofs, the one given by Pr\"ufer \cite{P18} is based on a
one-to-one correspondence between labeled trees and strings of
length $n-2$ over the alphabet $\{1, \ldots, n\}$. This bijection
is known as the Pr\"ufer code.
In 1970 R\'enyi and R\'enyi \cite{RR69} generalized the Pr\"ufer
bijective proof of Cayley's formula to count labeled $k$-trees,
i.e., one of the most natural generalizations of trees.
The class of $k$-trees, introduced by Harary and Palmer \cite{HP68}, can be
defined in the following recursive way:
\begin{enumerate}
\item A complete graph on $k$ nodes is a $k$-tree.
\item If $T'_k=(V,E)$ is a $k$-tree, $K\subseteq V$ is a $k$-clique
and $v\notin V$,\\ then $T_k=\left(V\cup \{v\}, E \cup \{(v,x)\,|\,x\in K\}\right)$
is also a $k$-tree.
\end{enumerate}
\noindent A labeled $k$-tree is a $k$-tree whose nodes are
assigned distinct labels. They showed the number of labeled
$k$-trees of $n$ nodes to be ${n \choose
k}\left(k(n-k)+1\right)^{n-k-2}$. This result gave birth to
sequences \seqnum{A036361}, \seqnum{A036362}, and \seqnum{A036506}
in Sloane's On-line Encyclopedia of Integer Sequences \cite{SP}.
The class of $k$-trees can be further generalized by relaxing the constraint in
item $2$ asking for the node set $K$ to be a clique. Graphs
belonging to this class, introduced by Todd \cite{T89}, are known
as the $k$-arch graphs.
A $k$-arch graph can be defined in the following recursive way:
\begin{enumerate}
\item A complete graph on $k$ nodes is a $k$-arch graph.
\item If $A'_k=(V,E)$ is a $k$-arch graph, $K\subseteq V$ of cardinality $k$
and $v\notin V$,\\ then $A_k=\left(V\cup \{v\}, E \cup \{(v,x)\,|\,x\in K\}\right)$
is also a $k$-arch graph.
\end{enumerate}
\noindent The class of $k$-arch graphs can be equivalently defined
as the smallest class such that:
\begin{enumerate}
\item A complete graph on $k$ nodes is a $k$-arch graph;
\item If $A_k'$, obtained by removing a node of degree $k$ from $A_k$, is a $k$-arch graph, then $A_k$ is a $k$-arch graph.
\end{enumerate}
\noindent A labeled $k$-arch graph is a $k$-arch graph whose nodes
are assigned distinct labels. In this paper we deal with labeled
$k$-arch graphs; we use integers in $[1,n]$ as node labels, where
$n$ always refers to $|V|$. When no confusion arises we identify a
node with its label. An example of a labeled $3$-arch graph on
$10$ nodes is given in Figure~\ref{fig:3arch}.
Note that when $k=1$ both $k$-trees and $k$-arch graphs are Cayley
trees.
An attempt to generalize the Pr\"ufer bijective proof of Cayley's
formula to count labeled $k$-arch graphs has been made by Lamathe
\cite{L04}. He established a correspondence relating $k$-arch
graphs and strings over the alphabet whose symbols are all
$k$-subsets of the vertex set of a given $k$-arch graph. He
claimed this correspondence to be a bijection and derived the
number of labeled $k$-arch graphs of $n$ nodes to be ${n\choose
k}^{n-k-1}$. Unfortunately this result is wrong, as the majority
of the strings do not represent any $k$-arch graph, meaning that
the shown correspondence is not a bijection (see
Section~\ref{sec:decoding} for an example of an invalid string).
Indeed, Lamathe's formula produces a serious overestimation of
the number of labeled $k$-arch graphs. In the following table we
show the overestimation ratio for certain values of $n$ and
$k$:
\begin{center}
\begin{tabular}{c|c|c|c}
$n \backslash k$ & 2 & 3 & 4 \\
\hline
10 & \hfill 1.6311 & \hfill 3.9045 & \hfill 5.4925 \\
15 & \hfill 4.8581 & \hfill 85.8627 & \hfill 806.9044 \\
20 & \hfill 18.8593 & \hfill 3699.9280 & \hfill 434531.3726 \\
\end{tabular}
\end{center}
\noindent The ratio dramatically increases when $n$ and $k$
increase; this implies that almost all strings do not correspond
to $k$-arch graphs. As an example, consider that when $n=200$ and
$k=185$, the ratio is $1.6681\times 10^{104}$.
The error made by Lamathe is to consider every possible string as
the encoding of some $k$-arch graph. Instead the subset of strings
resulting from encoding $k$-arch graphs needs to be correctly
characterized, in the same way that R\'enyi and R\'enyi did for $k$-trees.
In this paper we exhibit the flaw in the Lamathe's formula by
showing a simple counterexample. We provide a characterization
of valid strings, and then we exploit properties of those strings in
order to define a recursive function that computes the number of
labeled $k$-arch graphs of $n$ nodes, for any given $n$ and $k$.
% ---------------------------------------------------------------------- CODING
\section{Encoding $k$-arch Graphs}
Let $\mathcal{A}_k^n$ be the set of all $k$-arch graphs of $n$
nodes, let ${[1,n] \choose k}$ be the set of all $k$-subset of the
integer interval $[1,n]$, and let $\mathcal{B}_k^n$ be the set of
all possible strings of length $n-k-1$ over the alphabet ${[1,n]
\choose k}$. We use the notation $adj(v)$ to identify the set of
all nodes adjacent to a given node $v$, and the term
\emph{$k$-leaf} to mean a node $u$ such that $|adj(u)| = k$; any
other node $v$ has $|adj(v)|>k$ and is called \emph{internal}.
Let us define the following function:
$$
\rho(A_k^n) = \left\{%
\begin{array}{ll}
\varepsilon, & \hbox{if $A_k^n$ is a single $k+1$ clique;} \\[8pt]
adj(min\{v \in A_k^n : |adj(v)|=k\})::\rho(A_k^n \setminus \{v\}), & \hbox{otherwise.} \\
\end{array}%
\right.
$$
The function $\rho$ is the injective function between
$\mathcal{A}_k^n$ and $\mathcal{B}_k^n$ used by Lamathe, i.e., the
generalization made by R\'enyi and R\'enyi of the Pr\"ufer
bijection applied to $k$-arch graphs. The recursion described by
$\rho$ embodies a pruning of the $k$-arch graph $A_k^n$ that
starts from the smallest $k$-leaf $v$; as $v$ is removed from
$A_k^n$, its adjacent set constitutes the first symbol of the
string. This symbol is concatenated (by string concatenation
operator $::$) to the string obtained by recursively applying the
function to the pruned graph. The recursion terminates when the
pruning gives a clique on $k+1$ nodes, as $\rho$ applied to a
clique gives the empty string $\varepsilon$.
Note that, by definition of $k$-arch graphs, every subgraph
produced during the pruning process is a $k$-arch graph.
It is worth remarking that we are assuming $n > k$, as well as the
Pr\"ufer code assumes the tree to have at least 2 nodes. When
$n=k$, the only admissible $k$-arch graph is a single clique with
$|\mathcal{A}_k^k|=1$. When $n k+1$ nodes is
$|\mathcal{A}_k^n|=f_k^n(n-k-1,0,k)$ where $f_k^n$ is the
recursive function defined as:
$$
f_k^n(i,u,j)=\left\lbrace
\begin{array}{ll}
{{n-u}\choose j} {u\choose {k-j}},& \hbox{if $i=1$;}\\[10pt]
{{n-u}\choose j} {u\choose {k-j}} \displaystyle{ \stackrel{\min(k,n-(i-1)-(u+j))\hfill} {\sum_{c=0}{f_k^n(i-1,u+j,c)}}} ,& \hbox{otherwise.}\\
\end{array}
\right.
$$
\noindent When $n=k$ or $n=k+1$ $|\mathcal{A}_k^n|=1$; when $ni}B_j|$, i.e., the number of elements in $B_i$ that do
not appear in the substring $(B_{i+1},\ldots,B_l)$.
Consider the recursion tree generated by applying the function
$f_k^n$ to $(n-k-1,0,k)$. This tree is a generalization of the one
presented in Fig.~\ref{fig:recTree} for the special case $n=7$ and
$k=3$: node labels correspond to the binomials product and edge
labels correspond to the value of the variable $c$ discriminating
recursive applications of function $f_k^n$.
Notice that, considering the edge labels in any leaf to root path
of this tree, we obtain a vector $(c_1,\ldots, c_{n-k-2})$ which
represents the sequence of newly inserted numbers (from right to
left), and so it coincides with the characteristic of some string
in $\mathcal{C}_k^n$. It is also true that if $\overline{c}$ is
the characteristic of a string in $\mathcal{C}_k^n$, then a leaf
to root path whose edge labels vector is $\overline{c}$ must
exist.
$|\mathcal{C}_k^n|$ can be obtained by summing cardinalities of
disjoint sets of strings sharing the same characteristic. The size
of any such set is given by the product of node labels following
the corresponding leaf to root path in the recursion tree. By
summing those products, we thus obtain $|\mathcal{C}_k^n|$, i.e.,
the value computed by $f_k^n(n-k-1,0,k)$.
\end{proof}
% -------------------------------------------------------- EXPERIMENTAL RESULTS
\subsection{Experimental Results}
We implemented the recursive function to enumerate the labeled
$k$-arch graphs on $n$ nodes using the open source algebraic
system \emph{PARI/GP} ({\tt
\href{http://pari.math.u-bordeaux.fr/}{http://pari.math.u-bordeaux.fr/}}).
The code performing the counting is given in Figure~\ref{fig.code}.
\begin{figure}[h]
\hrule
\medskip
\begin{verbatim}
f(n,k,i,u,j)={
local(s=0);
if (i==1,
binomial(n-u,j)*binomial(u,k-j),
for (c=0, min(k,n-(i-1)-(u+j)),
s+=f(n,k,i-1,u+j,c)
);
binomial(n-u,j)*binomial(u,k-j)*s
)
}
\end{verbatim}
\hrule \caption{\label{fig.code} Code implementing the recursive
function $f_k^n$.}
\end{figure}
The size of the recursion tree is exponential in the order of
$(k+1)^{n-k-2}$ so the value can only be computed if the
difference between $n$ and $k$ is small. As done by Lamathe we
report values of $|\mathcal{A}_k^n|$ for $n \in [1,10]$ and
$k\in[1,7]$ in the following table:
\begin{center}
\noindent\begin{tabular}{c||r|r|r|r|r|r|r|r|r|r}
$k \backslash n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
1 & 1 & 1 & 3 & 16 & 125 & 1296 & 16807 & 262144 & 4782969 & 100000000\\
2 & 0 & 1 & 1 & 6 & 100 & 3285 & 177471 & 14188888 & 1569185136 & 229087571625\\
3 & 0 & 0 & 1 & 1 & 10 & 380 & 34405 & 5919536 & 1709074584 & 764754595200\\
4 & 0 & 0 & 0 & 1 & 1 & 15 & 1085 & 216230 & 92550276 & 74358276300\\
5 & 0 & 0 & 0 & 0 & 1 & 1 & 21 & 2576 & 982926 & 898027452\\
6 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 28 & 5376 & 3568950\\
7 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 36 & 10200\\
\end{tabular}
\end{center}
\noindent The first row of this table gives exactly the well-known
Cayley's formula, as $1$-arch graphs are trees. Apart from this
row (reported as Sequence \seqnum{A000272}) no other row of the
table is listed in the on-line Encyclopedia of Integer Sequences
\cite{SP}. Moreover Sequences \seqnum{A098721}, \seqnum{A098722},
\seqnum{A098723}, and \seqnum{A098724} should be updated to
reflect our correction of Lamathe's results (rows 2, 3, 4 of above
table respectively).
% ------------------------------------------------------------------ CONCLUSION
\section{Conclusion and Open Problems}
In this paper we have presented a recursive function that computes
the number of labeled $k$-arch graphs of $n$ nodes, for any given
$n$ and $k$. In order to obtain this function, we have used a code
that maps labeled $k$-arch graphs to strings and we have derived
the counting function by characterizing valid code strings.
Moreover, we have proved the counting function for $k$-arch graphs
provided by Lamathe to be incorrect by showing a counterexample.
It remains an open problem to find, provided that it exists, a
closed-form solution for the recursive function computing
$|\mathcal{A}_k^n|$, when $k>1$, perhaps exploiting generating functions.
When $k=1$, from Cayley's
formula, we have $|\mathcal{A}_1^n| = n^{n-2}$. Furthermore, it
would be interesting to investigate the case of rooted and unlabeled $k$-arch
graphs.
% ---------------------------------------------------------------- BIBLIOGRAPHY
\section*{Acknowledgments}
We want to thank Prof.\ Rossella Petreschi for her support and her
useful comments.
% ---------------------------------------------------------------- BIBLIOGRAPHY
\bibliography{resume}
\begin{thebibliography}{30}
\bibitem{C89} A. Cayley, A theorem on trees,
{\em Quarterly J. Math.} {\bf 23} (1889), 376--378.
\bibitem{HP68} F. Harary and E. M. Palmer, On acyclic simplicial
complexes, {\em Mathematika} {\bf 15} (1968), 115--122.
\bibitem{L04} C. Lamathe, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Lamathe/lamathe2.html}{The number of labelled $k$-arch graphs},
{\em J. Integer Sequences} {\bf 7} (2004), Article 04.3.1.
\bibitem{M67} J. W. Moon, Various proofs of Cayley's formula for counting
trees, In F. Harary, ed., {\em A Seminar on Graph Theory},
Holt, Rinehart and Winston, New York, 1967, Chapter 11, pp. 70--78.
\bibitem{P18} H. Pr\"ufer, Neuer Beweis eines Satzes \"uber Permutationen,
{\em Archiv der Mathematik und Physik} {\bf 27} (1918), 142--144.
\bibitem{RR69} C. R\'enyi and A. R\'enyi, The Pr\"ufer code for $k$-trees,
P. Erd\H{o}s et al., editors, {\em Combinatoral Theory and its Applications (Proc. Colloq. Balatonfured, 1969)}, North-Holland (1970), 945--971.
\bibitem{SP} N. J. A. Sloane, {\em The On-Line Encyclopedia of
Integer Sequences}, 2007,
\href{http://www.research.att.com/~njas/sequences}{\tt http://www.research.att.com/$\sim$njas/sequences}.
\bibitem{T89} P. Todd, A $k$-tree generalization that characterizes consistency of dimensioned engineering drawings,
{\em SIAM J. Disc. Math.} {\bf 2} (1989), 255--261.
\end{thebibliography}
\bigskip\hrule\bigskip
\noindent 2000 {\it Mathematics Subject Classification}: Primary
05A15, 05C30; Secondary 05A10.
\noindent {\it Keywords:} $k$-arch graphs, trees, $k$-trees,
coding, Pr\"{u}fer code, Cayley's formula.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences \seqnum{A000272},
\seqnum{A098721}, \seqnum{A098722}, \seqnum{A098723} and
\seqnum{A098724}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received November 3 2006;
revised version received July 16 2007.
Published in {\it Journal of Integer Sequences}, July 17 2007.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}