On the Number of Labeled k-arch Graphs
Saverio Caminiti and Emanuele G. Fusco
Department of Computer Science
University of Rome "La Sapienza"
Via Salaria 113
In this paper we deal with k
-arch graphs, a superclass of trees
-trees. We give a recursive function counting the number of
-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.
A previous attempt at counting the number of labeled k-arch graphs
was made by Lamathe. We point out an error in his work, and
prove it by giving a counterexample.
Full version: pdf,
(Concerned with sequences
Received November 3 2006;
revised version received July 16 2007.
Published in Journal of Integer Sequences, July 17 2007.
Journal of Integer Sequences home page