Journal of Integer Sequences, Vol. 10 (2007), Article 07.7.5

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
00198 Rome
Italy

Abstract:

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.

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,    dvi,    ps,    latex    

(Concerned with sequences A000272 A098721 A098722 A098723 and A098724 .)

Received November 3 2006; revised version received July 16 2007. Published in Journal of Integer Sequences, July 17 2007.

Return to Journal of Integer Sequences home page