The Number of Labelled k-Arch Graphs

Cédric Lamathe (1)

1 ISA - Models, algorithms and geometry for computer graphics and vision

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

Mots clés: generalization of trees; graphes de k-arches; k-arch graphs; prüfer code; code de prüfer; généralisation des arbres

Domaines: Autre [cs.OH]

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