On Large Vertex-Symmetric 2-Reachable Digraphs.
F.Comellas, M.A. Fiol , J.Gómez
Departament de Matemàtica Aplicada i Telemàtica;
Universitat Politècnica de Catalunya
Parallel Processing Letters, 4, pp. 379--384 (1994).
We are interested in the construction of the largest possible vertex
symmetric digraphs with the property that between any two vertices
there is a walk of length two (that is, they are 2-reachable).
Other than a theoretical interest, these digraphs and their generalizations
may be used as models of interconnection networks for implementing
parallelism. In these systems many nodes are connected with relatively few
links and short paths between them and each node may execute, without
modifications, the same communication software. On the other hand, a
message sent from any vertex reaches all vertices, including
the sender, in exactly two steps.
In this work we present families of vertex symmetric 2-reachable
digraphs with order attaining the upper theoretical bound
for any odd degree. Some constructions for even degree are also
given.
Load a preprint version of the article (may differ from the
final version):