Dense Trivalent Graphs for Processor Interconnection
Leland, Solomon · IEEE Transactions on Computers · 1982
This paper presents a new family of undirected graphs that allows N processors to be connected in a network of diameter 3/2 log2 N + O(1), while only requiring that each processor be connected to three neighbors. The best trivalent graphs previously proposed require a diameter of 2 log2N + O(1).