Tight-optimal circulants vis-脿-vis twisted tori

详细信息    查看全文

• 作者：Pranava K. Jha <sup>pkjha@stcloudstate.edu" class="auth_mailsup> <sup>pkjha384@hotmail.com" class="auth_mailsup>
• 关键词：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 <span id="mmlsi74" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si74.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=2127b8941452eb4e46ba48ad2dd67db9" title="Click to view the MathML source">(2a+d)aspan><span class="mathContainer hidden"><span class="mathCode">scroll">(2a+d)aspan>span>span> vertices for each <span id="mmlsi75" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si75.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=142875a672d92710e415e578d2fc8446" title="Click to view the MathML source">a≥5span><span class="mathContainer hidden"><span class="mathCode">scroll">a≥5span>span>span>, where <span id="mmlsi76" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si76.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=e11ce87a1c0d1e4b419d860595b0b28e" title="Click to view the MathML source">d=&minus;1,0,+1span><span class="mathContainer hidden"><span class="mathCode">scroll">d=&minus;1,0,+1span>span>span>. The step sizes in each case are <span id="mmlsi77" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si77.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=9658069979d59eb49b1c9a31463bd7d3" title="Click to view the MathML source">1span><span class="mathContainer hidden"><span class="mathCode">scroll">1span>span>span> and <span id="mmlsi78" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si78.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=75ad0000543f27104c4804fe1da32d90" title="Click to view the MathML source">(2a+d)k&minus;1span><span class="mathContainer hidden"><span class="mathCode">scroll">(2a+d)k&minus;1span>span>span>, where <span id="mmlsi79" class="mathmlsrc">source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si79.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=74b4cb2d1d2f2c49d6632e347a14ec9e">ss="imgLazyJSB inlineImage" height="15" width="90" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X14002236-si79.gif">script>style="vertical-align:bottom" width="90" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0166218X14002236-si79.gif">script><span class="mathContainer hidden"><span class="mathCode">scroll">style mathvariant="normal">gcdstyle>(a,k)=1span>span>span> and <span id="mmlsi80" class="mathmlsrc">source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si80.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=17d27cfc589b5cfe74be70a6c815b652">ss="imgLazyJSB inlineImage" height="21" width="130" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X14002236-si80.gif">script>style="vertical-align:bottom" width="130" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0166218X14002236-si80.gif">script><span class="mathContainer hidden"><span class="mathCode">scroll">1≤k≤⌊12(a&minus;1)⌋span>span>span>. For <span id="mmlsi81" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si81.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=8881f491e0bd467af39ca98b9ba07875" title="Click to view the MathML source">d=0span><span class="mathContainer hidden"><span class="mathCode">scroll">d=0span>span>span>, 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 <span id="mmlsi82" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si82.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=749524480b5c4d4d8965640b021a8a62" title="Click to view the MathML source">TT(2a+d,a)span><span class="mathContainer hidden"><span class="mathCode">scroll">TT(2a+d,a)span>span>span> by trading up to <span id="mmlsi83" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si83.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=4ae60c6853e0777b0d4106c58191b3b4" title="Click to view the MathML source">2aspan><span class="mathContainer hidden"><span class="mathCode">scroll">2aspan>span>span> edges for as many new edges, where <span id="mmlsi84" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si84.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=417b59fecbdcf77c7ff2c34d0661cb5b" title="Click to view the MathML source">d=&minus;1,+1span><span class="mathContainer hidden"><span class="mathCode">scroll">d=&minus;1,+1span>span>span>. 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 <span id="mmlsi85" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si85.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=195932ef2f13b80ea24dcb32988ae25d" title="Click to view the MathML source">aspan><span class="mathContainer hidden"><span class="mathCode">scroll">aspan>span>span> and <span id="mmlsi86" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14002236&_mathId=si86.gif&_user=111111111&_pii=S0166218X14002236&_rdoc=1&_issn=0166218X&md5=1cb425adff9fd75da311749faef8d986" title="Click to view the MathML source">kspan><span class="mathContainer hidden"><span class="mathCode">scroll">kspan>span>span>.