Cayley graphs of diameter two in interconnection networks

摘要

Modeling of interconnection networks is a problem from the area of Mechatronics, which is a multidisciplinary field of engineering. In the modeling of interconnection networks, basic limitations are given by physical characteristics of the proposed network. Since the networks are modeled by graphs, the limitations are maximum degree and diameter of the graphs. The problem to determine the largest order (number of vertices) n(d, k) of a graph with given maximum degree d and diameter k is known as the degree-diameter problem. There is a well known upper bound on the order — Moore bound. A special kind of graphs that are highly symmetric are Cayley graphs (these graphs are vertex transitive). In this contribution we present a construction for Cayley graps with c(d, 2) ≥ 8/25 d² valid for all degrees d ≥ 6.