佘衛強
數學與應用數學研究
邊故障增廣立方體通過指定邊的無故障哈密爾頓圈
佘衛強
(漳州職業技術學院 公共教學部,福建 漳州 363000)

增廣立方體;線性森林;哈密爾頓圈;網絡


令
且

由0導出的子圖是線性森林,則在AQ-中存在一條無故障哈密爾頓圈包含0的所有邊。








這里0連接0和0,1連接1和1。
對作數學歸納法證明。
當=4時,由引理2得到,定理1成立。

設
下面分兩種情況討論,其它情況都同構于這兩種情況中的某一種。

即存在

圖1 (u,v)和(s,t)沒有交點

圖2 (u,v)和(s,t)有交點

包含0,如圖3所示。

圖3 ,

所以取

包含E0,如圖4所示。
情況2 若
為方便表述假設

且
故在AQ-中存在一條無故障哈密爾頓圈
包含0,如圖4所示。
定理1歸納法證畢。
[1] H C Hsu, L C Chiang, J J M Tan, L H Hsu. Fault Hamiltonicity of augmented cubes[J]. Parallel Comput- ing, 2005, 31(1): 131-145.
[2] S Y Hsieh, Y R Cian. Conditional edge-fault Hamilton- icity of augmented cubes[J]. Inform Sci 2010, 180(13): 2596-2617.
[3] 佘衛強,增廣立方體中通過給定三條邊的哈密爾頓圈[J].漳州職業技術學院學報,2015,17(3):10-15.
[4] Wang W Q, Chen X B. A faulty free Hamilton cycle passing through prescribed edges in Hypercubes with faulty edges[J]. Inform Process Lett, 2007,107(2): 211- 215.
[5] Chen X B. Cycles passing through prescribed edges in hypercubes with some faulty edges[J]. Inform Process Lett, 2007, 104(2): 211-215.
[6] Wang S, Y Yang, J Li. Hamilton cycles passing through linear forests in k-ary nn-cubes[J]. Discrete Applied Mathematics, 2011, 159(14): 1425-1435.
[7] 佘衛強,邊故障增廣立方體中兩條無故障點不交路[J].閩南師范大學學報,2016,91(1):17-20.
[8] A Bondy, U S R. Murty, Graph Theorywith Applications [M]. Macmillan Press, London, 1976.
Fault-Free Hamilton Cycle Passing through Prescribed Edges in Augmented with Faulty Edges
SHE Wei-qiang
(Department of Public Teaching, Zhangzhou Institute of Technology, Zhangzhou 363000, China)

Augmented cube; Linear forest; Hamiltonian cycle; Network
O157.6
A
1009-9115(2019)06-0033-04
10.3969/j.issn.1009-9115.2019.06.008
國家自然科學基金項目(61603174)
2019-06-04
2019-09-22
佘衛強(1981-),男,福建東山人,碩士,副教授,研究方向為組合網絡。
(責任編輯、校對:趙光峰)