Degree 3 Undirected Variations on the Cube-Connected Cycles Network

摘要

It is an open question whether a network exists with N nodes, degree 3 and diameter log N + o(log N). Two of the best answers are the cube-connected cycles network CCC_n (n2~n nodes, diameter (5n/2)-2) and the Trivalent Cayley network TC_n (n2~n nodes, diameter 2n-1). Both CCC_n and TC_n are Cayley networks based on the same finite group. Many generating sets are shown which 1) have three elements, 2) are closed under inverse, and 3) result in Cayley networks with the same diameter as TC_n. It is also shown that all such generating sets result in networks with a structure similar to either CCC_n or TC_n. A network is introduced which is a variation of CCC_n, where nodes and edges are strategically added. This network has (n+2 n~(1/2) +2)2~n nodes, degree 3, and diameter (3n/2)+4 n~(1/2) +O(1), a step toward answering the open question.