Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.1

The Number of Labelled k-Arch Graphs


Cédric Lamathe
LORIA - INRIA Lorraine
Campus Scientifique, B.P. 239
54506 Vandoeuvre-lès-Nancy Cedex
France

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üfer code for trees. We also recover Cayley's formula $n^{n-2}$ that counts the number of labelled trees.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000272 A098721 A098722 A098723 and A098724.)

Received December 22 2003; revised version received July 1 2004. Published in Journal of Integer Sequences August 2 2004. Minor revisions (to add new sequences), March 16 2005.

Return to Journal of Integer Sequences home page