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.

05A15, 05C30, 05A10

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