\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