Circle Graphs: A New Class of Fixed Degree Interconnection Networks

Abstract

This paper suggests a novel graph Circle Graph(CG_n) with fixed degree of three. The node address of the CG_n is expressed with a n-binary number, along with degree of three, 3(2^(n-1)) edges, and 2^n nodes. In this paper, we suggest shortest-path routing algorithm for message transmission, and prove the diameter of CG_n is 2^(n-1) based on the routing algorithm outcome. Our CG_n possess the node symmetry and Hamilton cycle-structure. In addition, in this paper, we developed an algorithm to create parallel paths without node duplication.