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.
On the number of labeled k-arch graphs / Caminiti, Saverio; Fusco, EMANUELE GUIDO. - In: JOURNAL OF INTEGER SEQUENCES. - ISSN 1530-7638. - ELETTRONICO. - 10:7(2007), pp. 1-9.
On the number of labeled k-arch graphs
CAMINITI, SAVERIO;FUSCO, EMANUELE GUIDO
2007
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.