k-Pancyclicity of k-ary n-Cube Networks under the Conditional Fault Model

被引：11

作者：

Li, Jing ^{[1
]}

Liu, Di ^{[2
]}

机构：

[1] Taiyuan Univ Sci & Technol, Sch Appl Sci, Taiyuan 030024, Peoples R China

[2] NW Polytech Univ, Dept Appl Math, Xian 710129, Peoples R China

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 2012年 / 23卷 / 06期

基金：

中国国家自然科学基金;

关键词：

Interconnection networks; fault-tolerant; k-ary n-cube; k-pancyclicity; bipancyclicity; FREE HAMILTONIAN CYCLES; AUGMENTED CUBES; LINK FAULTS; TOLERANT PANCYCLICITY; CROSSED CUBES; LINEAR-ARRAY; EDGE FAULTS; PANCONNECTIVITY; EMBEDDINGS; BIPANCYCLICITY;

D O I：

10.1109/TPDS.2011.211

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The k-ary n-cube is one of the most popular interconnection networks for parallel and distributed systems. We prove that a k-ary n-cube with at most 4n - 5 faulty edges but where every vertex is incident with at least two healthy edges is k-pancyclic and bipancyclic for n >= 3 and odd k >= 3.

引用

页码：1115 / 1120

页数：6

共 33 条

[1]

[Anonymous], 2007, GRAPH THEORY

[2]

[Anonymous], P 38 IEEE COMP SOC I

[3] Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes [J].

Ashir, YA ;

Stewart, IA .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2002, 15 (03) :317-328

[4] Fault-free Hamiltonian cycles in twisted cubes with conditional link faults [J].

Fu, Jung-Sheng .

THEORETICAL COMPUTER SCIENCE, 2008, 407 (1-3) :318-329

[5] Edge-fault-tolerant vertex-pancyclicity of augmented cubes [J].

Fu, Jung-Sheng .

INFORMATION PROCESSING LETTERS, 2010, 110 (11) :439-443

[6] Embedding fault-free cycles in crossed cubes with conditional link faults [J].

Fu, Jung-Sheng ;

Hung, Hao-Shun ;

Chen, Gen-Huey .

JOURNAL OF SUPERCOMPUTING, 2009, 49 (02) :219-233

[7] Panconnectivity and edge-pancyclicity of 3-ary N-cubes [J].

Hsieh, Sun-Yuan ;

Lin, Tsong-Jie ;

Huang, Hui-Ling .

JOURNAL OF SUPERCOMPUTING, 2007, 42 (02) :225-233

[8] Hamiltonian path embedding and pancyclicity on the Mobius cube with faulty nodes and faulty edges [J].

Hsieh, Sun-Yuan ;

Chang, Nai-Wen .

IEEE TRANSACTIONS ON COMPUTERS, 2006, 55 (07) :854-863

[9] Conditional edge-fault Hamiltonicity of augmented cubes [J].

Hsieh, Sun-Yuan ;

Cian, Yi-Ru .

INFORMATION SCIENCES, 2010, 180 (13) :2596-2617

[10] PANCYCLICITY OF RESTRICTED HYPERCUBE-LIKE NETWORKS UNDER THE CONDITIONAL FAULT MODEL [J].

Hsieh, Sun-Yuan ;

Lee, Chia-Wei .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 23 (04) :2100-2119

← 1 2 3 4 →