HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

The Number of Labelled k-Arch Graphs

Cédric Lamathe 1
1 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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 is given by a simple integer sequence. 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 that counts the number of labelled trees. || Dans cette note, nous étudions les graphes de k-arches, une généralisation des arbres qui contiennent les k-arbres comme sous-classe. Nous montrons que le nombre de graphes de k-arches étiquetés aux sommets est donné par une suite d'entiers simples. A not
Document type :
Journal articles
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, October 19, 2006 - 3:48:02 PM
Last modification on : Friday, February 4, 2022 - 3:22:43 AM


  • HAL Id : inria-00108102, version 1



Cédric Lamathe. The Number of Labelled k-Arch Graphs. Journal of Integer Sequences, University of Waterloo, 2004, 7, 7 p. ⟨inria-00108102⟩



Record views