Tight-optimal circulants vis-à-vis twisted tori

In 1991, Tzvieli presented several families of optimal four-regular circulants. Prominent among them are three families that include graphs having (2a+d)a(2a+d)a vertices for each a≥5a≥5, where d=−1,0,+1d=−1,0,+1. The step sizes in each case are 11 and (2a+d)k−1(2a+d)k−1, where gcd(a,k)=1 and 1≤k≤⌊12(a−1)⌋. For d=0d=0, the graphs are called dense bipartite circulants, which were studied at length by the author recently. This paper examines the other two families and shows that the circulants in each of them are systematically obtainable from the twisted torus TT(2a+d,a)TT(2a+d,a) by trading up to 2a2a edges for as many new edges, where d=−1,+1d=−1,+1. In the process, the graphs seamlessly inherit all good characteristics of the twisted torus. In particular, each circulant in each family is tight-optimal, hence its average distance is the least among all circulants of the same order and size. Further, it admits a perfect dominating set under certain conditions on aa and kk.