On a generalization of Posthumus graphs

Abstract

In graph theory one often deals with 1-graphs (i. e.:given two vertices u and v, there is at last one arc that incides from u to v) of order $m=p^n$, where $p$ and $n$ are natural number greater than $1$. These are regular graphs of degree $p$ and diameter $n$, which have a certain importance in some problems of telecommunication (cf. [2], p.229: EXAMPLE), since vertices and arcs can respectively represent stations and one-way connections of a telecommunication network.

It seems that the first construction of these graphs, with $m=2^n$, is due to Ir. K. Posthumus, who stated a very interesting conjecture, concerning some cycles of digits 0 or 1, proved in [1] by N. G. De Bruijn.\\In the study of these graphs the condition $m=p^n$ is heavily relied on. In this paper we adapt that construction to the case in which $p^{n-1}<m\leq p^n$; so we find again several interesting properties of the previous particular case.\\Among other things, we get regular 1-graphs of degree $p$, such that for any two different vertices $u$ and $v$ there exists at least a path from $u$ to $v$ of length less than, or equal to, $n$.