Pancyclicity and bipancyclicity of folded hypercubes with both vertex and edge faults

详细信息查看全文

作者：Che-Nan Kuo ^{cn.kuo@mail.toko.edu.tw" class="auth_mail" title="E-mail the corresponding author}
关键词：Interconnection networks ; Folded hypercubes ; Pancyclicity ; Bipancyclicity ; Fault-tolerant ; Fault-free
刊名：Theoretical Computer Science
出版年：2015
出版时间：18 October 2015
年：2015
卷：602
期：Complete
页码：125-131
全文大小：328 K

文摘

A graph is said to be pancyclic if it contains cycles of every length from its girth to its order inclusive; and a bipartite graph is said to be bipancyclic if it contains cycles of every even length from its girth to its order. The pancyclicity or the bipancyclicity of a given network is an important factor in determining whether the network's topology can simulate cycles of various lengths. An n -dimensional folded hypercube an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si1.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=60a848fb4afe36823e748f434e3b6fc9" title="Click to view the MathML source">FQ_nan>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">FQnath>an>an>an> is a well-known variation of an n -dimensional hypercube an id="mmlsi113" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si113.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=fe448b2dbe8ad76531af4ad8b74987ef" title="Click to view the MathML source">Q_nan>an class="mathContainer hidden">an class="mathCode">ath altimg="si113.gif" overflow="scroll">Qnath>an>an>an> which can be constructed from an id="mmlsi113" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si113.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=fe448b2dbe8ad76531af4ad8b74987ef" title="Click to view the MathML source">Q_nan>an class="mathContainer hidden">an class="mathCode">ath altimg="si113.gif" overflow="scroll">Qnath>an>an>an> by adding an edge to every pair of vertices with complementary addresses. an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si1.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=60a848fb4afe36823e748f434e3b6fc9" title="Click to view the MathML source">FQ_nan>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">FQnath>an>an>an> for any odd n is known to bipartite. In this paper, let an id="mmlsi245" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si245.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=c513c19a1538d62b0e9846395c484df3" title="Click to view the MathML source">FF_van>an class="mathContainer hidden">an class="mathCode">ath altimg="si245.gif" overflow="scroll">FFvath>an>an>an> and an id="mmlsi246" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si246.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=7eec9e590b5e6470f0fc1195dc30ee29" title="Click to view the MathML source">FF_ean>an class="mathContainer hidden">an class="mathCode">ath altimg="si246.gif" overflow="scroll">FFeath>an>an>an> denote the sets of faulty vertices and faulty edges in an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si1.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=60a848fb4afe36823e748f434e3b6fc9" title="Click to view the MathML source">FQ_nan>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">FQnath>an>an>an>. Then, we consider the pancyclicity and bipancyclicity properties in an id="mmlsi136" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si136.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=33dfb5ced187d2fe5485aa404ecf66ce" title="Click to view the MathML source">FQ_n−FF_v−FF_ean>an class="mathContainer hidden">an class="mathCode">ath altimg="si136.gif" overflow="scroll">FQn−FFv−FFeath>an>an>an>, as follows:

ass="label">1.: For an id="mmlsi118" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si118.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=42618fe2d13e39450a23308293093307" title="Click to view the MathML source">n≥3an>an class="mathContainer hidden">an class="mathCode">ath altimg="si118.gif" overflow="scroll">n≥3ath>an>an>an>, an id="mmlsi136" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si136.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=33dfb5ced187d2fe5485aa404ecf66ce" title="Click to view the MathML source">FQ_n−FF_v−FF_ean>an class="mathContainer hidden">an class="mathCode">ath altimg="si136.gif" overflow="scroll">FQn−FFv−FFeath>an>an>an> contains a fault-free cycle of every even length from 4 to an id="mmlsi127" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si127.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=bf118f631243471e87227e062b1bb799" title="Click to view the MathML source">2ⁿ−2⋅|FF_v|an>an class="mathContainer hidden">an class="mathCode">ath altimg="si127.gif" overflow="scroll">2n−2⋅alse">|FFvalse">|ath>an>an>an>, where an id="mmlsi135" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si135.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=b54d81d2f166a3326d75f28712d5eaf5" title="Click to view the MathML source">|FF_v|+|FF_e|≤n−1an>an class="mathContainer hidden">an class="mathCode">ath altimg="si135.gif" overflow="scroll">alse">|FFvalse">|+alse">|FFealse">|≤n−1ath>an>an>an>;
ass="label">2.: For an id="mmlsi218" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si218.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=5c74c9fdb268a0a2dd6b3258b3c4c605" title="Click to view the MathML source">n≥4an>an class="mathContainer hidden">an class="mathCode">ath altimg="si218.gif" overflow="scroll">n≥4ath>an>an>an> is even, an id="mmlsi136" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si136.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=33dfb5ced187d2fe5485aa404ecf66ce" title="Click to view the MathML source">FQ_n−FF_v−FF_ean>an class="mathContainer hidden">an class="mathCode">ath altimg="si136.gif" overflow="scroll">FQn−FFv−FFeath>an>an>an> contains a fault-free cycle of every odd length from an id="mmlsi10" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si10.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=17960a1a6a308bcb44c3bdbdfcb3601a" title="Click to view the MathML source">n+1an>an class="mathContainer hidden">an class="mathCode">ath altimg="si10.gif" overflow="scroll">n+1ath>an>an>an> to an id="mmlsi11" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si11.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=90dd19a1b56f65999b88815e1ba8779e" title="Click to view the MathML source">2ⁿ−2⋅|FF_v|−1an>an class="mathContainer hidden">an class="mathCode">ath altimg="si11.gif" overflow="scroll">2n−2⋅alse">|FFvalse">|−1ath>an>an>an>, where an id="mmlsi135" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007653&_mathId=si135.gif&_user=111111111&_pii=S0304397515007653&_rdoc=1&_issn=03043975&md5=b54d81d2f166a3326d75f28712d5eaf5" title="Click to view the MathML source">|FF_v|+|FF_e|≤n−1an>an class="mathContainer hidden">an class="mathCode">ath altimg="si135.gif" overflow="scroll">alse">|FFvalse">|+alse">|FFealse">|≤n−1ath>an>an>an>.

地址：北京市海淀区学院路29号邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700