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.
2007
k-trees; trees; cayley's formula; prüfer code; k-arch graphs; coding
01 Pubblicazione su rivista::01a Articolo in rivista
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.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/361539
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact