On a generalization of Posthumus graphs

doi:10.1285/i15900932v20n2p21

On a generalization of Posthumus graphs

Domenico Lenzi

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

کاغذ a4

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

Username
Password
Remember me

Note di Matematica

On a generalization of Posthumus graphs

Abstract