Large butterfly Cayley graphs and digraphs

Research output: Contribution to journalArticle

We present families of large undirected and directed Cayley graphs whose construction is related to butterfly networks. One approach yields, for every large k and for values of d taken from a large interval, the largest known Cayley graphs and digraphs of diameter k and degree d. Another method yields, for sufficiently large k and infinitely many values of d, Cayley graphs and digraphs of diameter k and degree d whose order is exponentially larger in k than any previously constructed. In the directed case, these are within a linear factor in k of the Moore bound.

    Research areas

  • Cayley graphs, degree–diameter problem, butterfly networks, Moore bound

View graph of relations