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.


DOI Code: 10.1285/i15900932v20n2p21

Keywords: Graph

Classification: 05CXX

Full Text: PDF


Creative Commons License
This work is licensed under a Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia License.