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 <>
Submitted on : Thursday, October 19, 2006 - 3:48:02 PM
Last modification on : Friday, February 26, 2021 - 3:28:03 PM


  • 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