Dense bipartite circulants and their routing via rectangular twisted torus

作者：Jha Pranava K^*

来源：Discrete Applied Mathematics, 2014, 166: 141-158.

DOI：10.1016/j.dam.2013.09.021

• Circulant graphs
• Rectangular twisted torus
• Fault tolerance
• Multiprocessor interconnection
• Network topology
• Graphs and networks

Whereas the maximum number of vertices in a four-regular circulant of diameter a is 2a(2) + 2a + 1, the bound turns out to be 2a(2) if the condition of bipartiteness is imposed. Tzvieli presented a family of psi(a) such dense bipartite circulants on 2a(2) vertices for each a >= 3, where psi(a) denotes the number of positive integers less than or equal to left perpendicular1/2(a - 1)right perpendicular that are coprime with a. The present paper shows that each of those graphs is obtainable from the 2a x a rectangular twisted torus by appropriately trading a maximum of 2a edges for as many new edges. The underlying structural similarity between the two graphs leads to a simple intuitive routing algorithm for the circulants. The result closely parallels the routing in dense nonbipartite circulants on 2a(2) + 2a + 1 vertices. Additional results include a set of vertex-disjoint paths between every pair of distinct vertices in the circulants, and a proof that the 2a x a rectangular twisted torus itself is probably not a circulant.

• 出版日期2014-3-31