邊故障增廣立方體通過指定邊的無故障哈密爾頓圈

佘衛強

數學與應用數學研究

邊故障增廣立方體通過指定邊的無故障哈密爾頓圈

佘衛強

（漳州職業技術學院 公共教學部，福建 漳州 363000）

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

令

且

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

1 引言

這里0連接0和0，1連接1和1。

2 定理1的證明

對作數學歸納法證明。

當=4時，由引理2得到，定理1成立。

設

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

即存在

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

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

包含0，如圖3所示。

圖3 ，

所以取

包含E0，如圖4所示。

情況2 若

為方便表述假設

且

故在AQ-中存在一條無故障哈密爾頓圈

包含0，如圖4所示。

定理1歸納法證畢。

3 結束語

[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-），男，福建東山人，碩士，副教授，研究方向為組合網絡。

（責任編輯、校對：趙光峰）