Dense bipartite circulants and their routing via rectangular twisted torus

Whereas the maximum number of vertices in a four-regular circulant of diameter a is 2a2+2a+1, the bound turns out to be 2a2 if the condition of bipartiteness is imposed. Tzvieli presented a family of ψ(a) such dense bipartite circulants on 2a2 vertices for each a≥3, where ψ(a) denotes the number of positive integers less than or equal to ⌊12(a−1)⌋ that are coprime with a. The present paper shows that each of those graphs is obtainable from the 2a×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 2a2+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×a rectangular twisted torus itself is probably not a circulant.