\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[latin1]{inputenc}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\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}

\begin{center}
\vskip 1cm{\LARGE\bf 
The Number of Labelled $k$-Arch Graphs
}
\vskip 1cm
\large
C\'edric Lamathe\\
LORIA - INRIA Lorraine\\
Campus Scientifique, B.P. 239\\
54506 Vandoeuvre-l\`es-Nancy Cedex, France\\
\href{mailto:lamathe@loria.fr}{\tt lamathe@loria.fr} \\
\end{center}

\vskip .2 in

\begin{abstract}
In this note, we deal with $k$-arch graphs, a generalization of trees,
which contain $k$-trees as a subclass. We show that the number of
vertex-labelled $k$-arch graphs with $n$ vertices, for a fixed integer $k\geq 1$, is
${n\choose k}^{n-k-1}$. As far as we know, this is a new integer
sequence. We establish this result with a one-to-one correspondence
relating $k$-arch graphs and words whose letters are $k$-subsets of
the vertex set. This bijection generalises the well-known Pr\"{u}fer
code for trees. We also recover Cayley's formula $n^{n-2}$
that counts the number of labelled trees.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 

%\usepackage[dvips]{epsfig} 
%\usepackage{color} 
%\usepackage{float}


%%%%%%%%%%%%%%%%%%PERSONAL DEFINITIONS%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\R}{\mathbb R} 
\newcommand{\N}{\mathbb N}                                                     
\newcommand{\Z}{\mathbb Z} 
\newcommand{\Q}{\mathbb Q} 
\newcommand{\K}{\mathbb K} 
\newcommand{\A}{\mathbb A} 
\newcommand{\Sym}{\mathbb S} 


%\theoremstyle{plain}
%\theoremstyle{remark}

\newtheorem{theo}{\bf Theorem}
\newtheorem{de}{\bf Definition}
\newtheorem{lem}{\bf Lemma}
\newtheorem{cor}{\bf Corolary}
\newtheorem{prop}{\bf Proposition}
\newtheorem{rem}{\bf Remark}
\newtheorem{ex}{\bf Example}


\newenvironment{preuve}{\begin{trivlist}\item{\bf{Proof.}}} 
{\hfill\rule{2mm}{2mm}\end{trivlist}}  

\newcommand{\ark}{\mathcal{G}} 


\section{Introduction} 
We recursively define the class of $k$-{\em arch graphs}, for $k\geq
1$, as the smallest class of simple graphs such that:
\begin{itemize}
\item[1.] a $(k-1)$-simplex (i.e., a complete graph on $k$ vertices) 
is a $k$-arch graph;
\item[2.] if a simple graph $G$ has a vertex $v$ of degree $k$
such that the graph $G-\lbrace v \rbrace $ obtained from $G$ by removing $v$ and
its incident edges is a $k$-arch graph, then $G$ is a $k$-arch graph.
\end{itemize}
Figure~\ref{fig:arch} shows an unlabelled $2$-arch graph (we simply
say {\em arch graph} in this case) and a vertex-labelled
$2$-arch graph, each one built over 12 vertices. Note that, when $k=1$,
$1$-arch graphs coincide with (Cayley) trees. In a
constructive way, to build a $k$-arch graph of $n+1$ vertices from one
on $n$ vertices, we have to choose $k$ vertices and join the new
vertex to these selected vertices. The term {\it arch} evokes attaching
the new vertex over the $k$ chosen vertices.

%
\begin{figure}[ht] 
 \centerline{\includegraphics[width=.99\textwidth]{arch-unl-lab}} 
  \caption{Arch graphs on 12 vertices a) unlabelled, b) vertex-labelled.} 
  \label{fig:arch} 
\end{figure}
%

There are few papers about $k$-arch graphs, apart from \cite{T}, where
these graphs seem to appear, and \cite{L}. However, there is an
abundant literature about a subclass of $k$-arch graphs, called
$k$-trees, studied since the later 1960's. The essential difference
between $k$-trees and $k$-arch graphs lie in the fact that for
$k$-trees, we assume that the vertex $v$ is attached to $k$ mutually
adjacent vertices (that is, it forms a complete graph on $k+1$
vertices). For instance, see \cite{BP,M-69} for the labelled
enumeration of $k$-trees, and \cite{BM,P} for the particular case
$k=2$. Harary and Palmer \cite{HP} treat the unlabelled enumeration as
well as Fowler et al. \cite{TF}, who provide in addition asymptotic
formulas. We also mention
\cite{LLL-JCT,BL} for the enumeration of generalizations of 2-trees 
and \cite{these}, where various specializations of 2-trees are
enumerated. Finally, Labelle et al. \cite{LLL-TCS} propose a
classification of outerplanar 2-trees according to their
symmetries. Although $k$-trees have been extensively studied,
unlabelled enumeration of these structures is still an open
problem. Apart from enumerative aspects of 2-trees, Leclerc and
Makarenkov \cite{LM} give a correspondence between tree functions and
2-trees in the framework of tree metrics and tree dissimilarities (see
\cite{BG1,BG2}).

In \cite{T,L}, $k$-arch graphs are defined as maximal $kd$-acyclic
graphs, where a graph is said $kd$-acyclic, if it contains no
$kd$-cycle (see \cite{L}, definition 3.1). Todd shows that this
definition is equivalent to the recursive one given above. Leclerc
uses valuated arch graphs (that is, arch graph with valuated edges) to
encode tree distances or tree functions (see \cite{BG1,BG2}).\\

We recall that the number of labelled $k$-trees over $n$ vertices is
given by (\cite{BP,M-69}) 
\begin{equation}\label{ktrees}
a_n^k = {n\choose k}\left(k(n-k)+1\right)^{n-k-2}.
\end{equation}
When $k=1$, we recover the well-known Cayley formula
$a_n=n^{n-2}$ counting labelled (Cayley) trees.\\

The aim of this note is to obtain the number of labelled $k$-arch
graphs. We show this number is
\[
{n\choose k}^{n-k-1}.
\]
To achieve our goal, we propose in Section 2 a one-to-one
correspondence between $k$-arch graphs on $n$ vertices and words of
length $n-k-1$ whose letters are $k$-subsets of the set of vertex
labels. This correspondence generalizes the Pr\"{u}fer code for trees
(\cite{Prufer}).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The number of labelled $k$-arch graphs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section, we establish a formula giving the number of labelled
$k$-arch graphs, for $k\geq 1$. We prove this formula using a
bijective argument based on a generalization of the Pr\"{u}fer code
for vertex-labelled Cayley trees (\cite{Prufer}) which has been
generalized for $k$-trees (\cite{RR}). Note that formula
(\ref{number}) first appear (without proof) in the conclusion of
\cite{these}.

We call {\em leaf} of a $k$-arch graph, a vertex of degree $k$. For
instance, in Figure~\ref{fig:arch} b), there are four leaves,
respectively labelled 2,3,4,9. This definition of leaf is legitimate
since, for the special case $k=1$, a vertex of degree one in a Cayley
tree is a leaf, in the common sense of graph theory.

%
\medskip
%
\begin{prop}\label{prop}
Let $k\geq 1$ be a fixed integer. Then, the number $\ark^k_n$ of
$k$-arch graphs over $n$ labelled vertices, for $n>k$, is given by
\begin{equation}\label{number}
\ark_n^k = {n\choose k}^{n-k-1}\quad {\rm and}\qquad \ark_k^k=1.
\end{equation}
\end{prop}
%
\begin{preuve}
We construct a one-to-one correspondence between $k$-arch graphs on
$n$ labelled vertices and words $w=w_1w_2\ldots w_{n-k-1}$ of length
$n-k-1$ where each $w_i$ is a (valid) $k$-letter of the following
form:
\begin{equation}
\begin{pmatrix}
        v_{i_1}\\
        v_{i_2}\\
        \vdots \\
        v_{i_k}         
\end{pmatrix}
\end{equation}
such that
\begin{enumerate}
\item for all $1\leq j\leq k$, $1\leq i_j\leq n$; 
\item for all $1\leq j\leq n$, $v_j$ is a vertex of the $k$-arch graph;
\item $i_1<i_2<\cdots <i_k$.
\end{enumerate}
Such words are called {\em valid}. We implicitly assume that an order
is given on the labels, i.e., $v_1<v_2<\ldots <v_n$.  The
one-to-one correspondence works by successive leaf deletions. Let $g$
be a $k$-arch graph on $n$ vertices with vertex set
$V=\{v_1,v_2,\ldots,v_n\}$.  At the first step, we choose the leaf
with the smallest label in $g$, we remove it from $g$ as well as its
incident edges and form a $k$-letter with its adjacent vertices by
ordering them in increasing order. The fact that the degree of a leaf
is $k$ and the vertex ordering ensure we can always form a unique
valid $k$-letter. After the first leaf deletion, we obtain a $k$-arch
graph with $n-1$ vertices and we repeat the first step. Repeating this
step $n-k-1$ times, we get a valid word of length $n-k-1$. Observe
that after the last step, the $k$-arch graph $g$ becomes a single
$k-1$-simplex, that is, a complete graph on $k$ vertices. For
instance, if we apply this construction to the arch graph of
Figure~\ref{fig:arch} b), we obtain the following valid word of length
9:
\begin{equation}\label{word}
 \left(
\begin{array}{ccccccccc}
            1 & 7& 1& 8& 7& 5& 8& 8& 10\\
            6 & 11& 6& 11& 11& 12& 10& 7& 11\\
\end{array}\right).
\end{equation}
%
\\
\noindent Conversely, given a valid word $w=w_1w_2\ldots w_{n-k-1}$ of 
length $n-k-1$, we want to construct a $k$-arch graph with $n$
labelled vertices. Together with $w$, we use a dynamic subset $L$ of
the vertex set $V$, that is, a subset with evolving entries and
size. At the beginning, we fill $L$ with all vertices not appearing in
$w$ and we extend $w$ by appending a copy of the last $k$-letter,
$w_{n-k-1}$, at the end of $w$. We also denote $w$ this extended word
\[
w:=w||w_{n-k-1} = w_1w_2\ldots w_{n-k-1}w_{n-k-1}.
\]
For instance, according to the labelled $k$-arch graph of
Figure~\ref{fig:arch} b), we obtain $L=\{2,3,4,9\}$ and $w$ becomes
\[
\left(
\begin{array}{cccccccccc}
            1 & 7& 1& 8& 7& 5& 8& 8& 10&10\\
            6 & 11& 6& 11& 11& 12& 10& 7& 11&11\\
\end{array}\right).
\]
We remove the smallest element of $L$ and join it to every entry of
the first $k$-letter ($w_1$) of $w$. We then delete $w_1$ from $w$ and
still call $w$ this reduced word. We update $L$ by adding every vertex
$v_i\in w_1$ not appearing in the remaining letters of $w$. We repeat
the above recursive step with the word $w=w_2\ldots
w_{n-k-1}w_{n-k-1}$, and so on until we reach the empty word, keeping
at each step the connected component created. To end the converse map,
we have to connect together the $k$ vertices of the last $k$-letter
$w_{n-k-1}$ of $w$.\\

\noindent 
We have to verify that we obtain a connected graph which is a $k$-arch
graph corresponding to the word $w$ when the leaf deletion algorithm
is applied. It is quite straightforward using a recursive argument, as
the reader can check.
\end{preuve}
%

\medskip

Figure~\ref{bijection} shows a complete example of the reverse map for
a labelled arch graph of six vertices.
%
\begin{figure}[h] 
 \centerline{\includegraphics[width=.99\textwidth]{bijection}} 
  \caption{Illustration of the reverse map.} 
  \label{bijection} 
\end{figure}
%

\medskip

\begin{rem}
It is interesting to note that, for $k=1$, formula (\ref{number})
remains valid. Indeed, this formula becomes Cayley formula
($a_n=n^{n-2}$) enumerating trees with $n$ labelled vertices.
\end{rem}

\begin{rem}
The converse map constructed in the proof of Proposition~\ref{prop}
induces easily an algorithm of random generation of labelled $k$-arch
graphs by means of valid words.
\end{rem}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The following table gives the first few values of the number of
$k$-arch graphs over $n$ labelled vertices, for $k$ from 1 up to 7,
and for $n$ from $k$ up to 10. Only the first line of this table
(corresponding to Cayley formula $a_n=n^{n-2}$) is listed in the
on-line Encyclopedia of Integer Sequences \cite{SP} (sequence
A000272).
\medskip

In this note, we showed by a bijective way that the number of labelled
$k$-arch graphs is given by a new integer sequence. The class of
$k$-arch graphs are a natural multidimensional generalization of
trees, encompassing $k$-trees. To go further in the study of $k$-arch
graphs, we have to wonder about the unlabelled enumeration of these
graphs. Unfortunately, no result is known about the unlabelled
enumeration of both $k$-arch graphs and $k$-trees.


\begin{center}{\footnotesize
\begin{table}[H]
{\begin{tabular}{|c||l|l|l|l|l|l|l|l|l|l|l}
\hline
\rule{0mm}{.4cm} \raisebox{.4ex}[1.2ex][1.2ex]{$k\backslash n$}&1&2&3&4&5&6&7&8&9&10\\
\hline
\hline
1&1&1&3&16&125&1296&16807&262144&4782969&100000000\\
\hline
2&-&1&1&6&100&3375&194481&17210368&2176782336&373669453125\\
\hline
3&-&-&1&1&10&400&42875&9834496&4182119424&2985984000000\\
\hline
4&-&-&-&1&1&15&1225&343000&252047376&408410100000\\
\hline
5&-&-&-&-&1&1&21&3136&2000376&4032758016\\
\hline
6&-&-&-&-&-&1&1&28&7056&9261000 \\
\hline
7&-&-&-&-&-&-&1&1&36&14400 \\
\hline
%\hline
\end{tabular}}
\caption{Values of $\ark_n^k$, for $1\leq k\leq 7$ and $k\leq n\leq 10$.}
\end{table}
}
\end{center}

\section{Acknowledgments}

We greatly thank Bruno Leclerc for his presentation of $k$-arch graphs in
a Montreal seminar (LaCIM seminar, Universit\'e du Qu\'ebec \`a Montr\'eal) and Pierre Leroux for useful
discussions.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%       REFERENCES           %%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\bibliography{resume} 
\begin{thebibliography}{30} 
  
\bibitem{BG1} J. P. Barth\'elemy et A. Gu\'enoche, {\em Les Arbres 
et les Repr\'esentations des Proximit\'es}, Masson, 1988.

\bibitem{BG2} J. P. Barth\'elemy and A. Gu\'enoche, {\em Trees and 
Proximity Representations}, Wiley-Interscience Series in Discrete
Mathematics and Optimization, 1991.

\bibitem{BM} L. W. Beineke and J. W. Moon, Several proofs of the 
number of labeled 2-dimensional trees, in F. Harary ed., {\em Proof
Techniques in Graph Theory}, Academic Press, 1969, pp. 11--20.

\bibitem{BP} L. W. Beineke and R. Pippert, The number of labeled 
$k$-dimensional trees, {\em J. Combin. Theory} {\bf 6} (1969),
200--205.
 
\bibitem{BL} M. Bousquet and C. Lamathe, Enumeration of 
solid 2-trees, in Proceedings of the $14^{\rm th}$ international
conference Formal Power Series and Algebraic Combinatorics (FPSAC'02),
2002, pp. 133--147.

\bibitem{TF} T. Fowler, I. Gessel, G. Labelle, P. Leroux, The
    specification of 2-trees, {\em Adv. in Appl. Math.} {\bf 28}
    (2002), 145--168.
  
\bibitem{HP} F. Harary and E. Palmer, {\it Graphical Enumeration},
  Academic Press, 1973.
 
\bibitem{LLL-JCT} G. Labelle, C.
  Lamathe and P. Leroux, Labelled and unlabelled enumeration of
  $k$-gonal 2-trees, {\em J. Combin. Theory Ser. A} {\bf 106} (2004),
  193--219.

\bibitem{LLL-TCS} G. Labelle, C. Lamathe and P. Leroux, 
A classification of plane and planar 2-trees, {\em
Theoret. Comput. Sci.} {\bf 307} (2003), 337--363.

\bibitem{these} C. Lamathe, {\em Sp\'ecification de classes de 
structures arborescentes}, Ph.D. dissertation, Universit\'e du Qu\'ebec \`a Montr\'eal,
(2003).

\bibitem{L} B. Leclerc, Graphes d'arches, {\em Math. $\&$ Sci. 
humaines} {\bf 157} (2002), 27--48.
  
\bibitem{LM} B. Leclerc and V. Makarenkov, On some relations between 
2-trees and tree metrics, {\em Discrete Math.} {\bf 192} (1998),
223--249.

\bibitem{M-69} J. W. Moon, The number of
    labeled $k$-trees, {\em J. Combin. Theory} {\bf 6} (1969),
    196--199.

\bibitem{P} E. Palmer, On the number of
    labeled 2-trees, {\em J. Combin. Theory} {\bf 6} (1969), 206--207.

\bibitem{Prufer} H. Pr\"{u}fer, Neuer Beweis eines Satzes \"{u}ber 
Permutationen, {\em Arch. Math. Phys.} {\bf 27} (1918), 742--744.

\bibitem{RR} C. R\'enyi and A. R\'enyi, The Pr\"{u}fer code for $k$-trees, 
in {\em Combinatoral theory and it's applications}
(Proc. Colloq. Balatonf\"{u}red, 1969), North-Holland, 1970,
pp. 945--971.

\bibitem{SP} N. J. A. Sloane and S. Plouffe, {\em The 
Encyclopedia of Integer Sequences}, Academic Press, 1995.
\htmladdnormallink{\tt http://www.research.att.com/$\sim$njas/sequences}{http://www.research.att.com/~njas/sequences}

\bibitem{T} 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


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15, 05C30; Secondary 05A10.

\noindent \emph{Keywords:}
$k$-arch graphs, Pr\"{u}fer code, 
generalization of trees.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000272},
\seqnum{A098721},
\seqnum{A098721},
\seqnum{A098723} and
\seqnum{A098724}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 22 2003;  
revised version received  July 1 2004.
Published in {\it Journal of Integer Sequences}, August 2 2004.
Minor revision (to add new sequences), March 16 2005.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in


\end{document}