An Extension of the R\'enyi Formula

Abstract:

      In this paper, as a natural extension of the R\'enyi formula which counts labeled connected unicyclic graphs, we present a formula for the number of labeled $(k+1)$-uniform $(p,~q)$-unicycles as follows: $$U_{p,~q}^{(k+1)}=\begin{cases} \frac{p!}{2[(k-1)!]^q}\cdot \sum_{t=2}^q \frac{q^{q-t-1}\cdot {\rm sgn}(tk-2)}{(q-t)!}, & p=qk, \\ 0, & p\neq qk, \end{cases}$$ where $k,~p,~q$ are positive integers.