Tight-optimal circulants vis-脿-vis twisted tori

详细信息    查看全文

• 作者：Pranava K. Jha ^{pkjha@stcloudstate.edu" class="auth_mail pkjha384@hotmail.com" class="auth_mail}
• 关键词：Tight-optimal circulants ; Twisted tori ; Network topology ; Graphs and networks ; Chordal rings ; Double-loop graphs
• 刊名：Discrete Applied Mathematics
• 出版年：1 October 2014
• 年：2014
• 卷：175
• 期：Complete
• 页码：24-34
• 全文大小：1624 K

文摘

In 1991, Tzvieli presented several families of optimal four-regular circulants. Prominent among them are three families that include graphs having X14002236&_mathId=si74.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=2127b8941452eb4e46ba48ad2dd67db9" title="Click to view the MathML source">(2a+d)ami>ami>+<mi>dmi>)<mi>ami> vertices for each 142875a672d92710e415e578d2fc8446" title="Click to view the MathML source">a≥5mi>ami>≥5, where d=&minus;1,0,+1mi>dmi>=&minus;1,0,+1. The step sizes in each case are 1$1$ and (2a+d)k&minus;1mi>ami>+<mi>dmi>)<mi>kmi>&minus;1, where middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X14002236-si79.gif">mi>gcdmi>(<mi>ami>,<mi>kmi>)=1 and mi>kmi>≤⌊12(<mi>ami>&minus;1)⌋. For d=0mi>dmi>=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)mi>Tmi><mi>Tmi>(2<mi>ami>+<mi>dmi>,<mi>ami>) by trading up to 2ami>ami> edges for as many new edges, where d=&minus;1,+1mi>dmi>=&minus;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 ami>ami> and kmi>kmi>.