ON LARGE VERTEX SYMMETRIC 2-REACHABLE DIGRAPHS
Francesc Comellas, Miquel Àngel Fiol, J. Gómez · Parallel Processing Letters · 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.