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
Type de document :
Article dans une revue
Journal of Integer Sequences, University of Waterloo, 2004, 7, 7 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00108102
Contributeur : Publications Loria <>
Soumis le : jeudi 19 octobre 2006 - 15:48:02
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00108102, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

95