Caminiti, Saverio; Fusco, Emanuele G.

On the number of labeled $k$-arch graphs

J. Integer Seq. 10(7), Article 07.7.5, 9 p., electronic only (2007)


Summary: In this paper we deal with $k$-arch graphs, a superclass of trees and $k$-trees. We give a recursive function counting the number of labeled $k$-arch graphs. Our result relies on a generalization of the well-known Prüfer code for labeled trees. In order to guarantee the generalized code to be a bijection, we characterize the valid code strings.

Mathematics Subject Classification

05A15, 05C30, 05A10


k-arch graphs, trees, k-trees, coding, pr$\ddot $ufer code, Cayley's formula