Fault-Tolerant Cycle Embedding in Cartesian Product Graphs: Edge-Pancyclicity and Edge-Bipancyclicity with Faulty Edges

被引：7

作者：

Cheng, Chia-Wen ^{[1
]}

Hsieh, Sun-Yuan ^{[1
]}

机构：

[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 701, Taiwan

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 2015年 / 26卷 / 11期

关键词：

Cartesian product graphs; edge-bipancyclic; edge-pancyclic; fault-tolerant embedding; graph theoretical interconnection networks; ALTERNATING GROUP GRAPHS; INTERCONNECTION NETWORKS; N-CUBES; HYPERCUBES; DIAMETER;

D O I：

10.1109/TPDS.2014.2364604

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A graph G is called kappa-edge-fault edge-bipancyclic (kappa-edge-fault edge-r-pancyclic) if after deleting kappa edges from G, every edge in the resulting graph lies in a cycle of every even length from 4 to vertical bar V(G)vertical bar (a cycle of every length from r to vertical bar V(G)vertical bar), inclusively. In this paper, given two graphs G and H, which satisfy some specific properties, the edge-fault edge-bipancyclicity and edge-fault edge-r-pancyclicity (r is decided on the properties of G and H) of Cartesian product graphs G x H are efficiently evaluated. The obtained results are applied to two multiprocessor systems, the nearest neighbor mesh hypercubes and generalized hypercubes, both of which belong to Cartesian product graphs.

引用

页码：2997 / 3011

页数：15

共 36 条

[1]

Akers S. B., 1986, Proceedings of the 1986 International Conference on Parallel Processing (Cat. No.86CH2355-6), P216

[2]

Akl S. G., 1987, PARALLEL COMPUTATION

[3]

BHUYAN LN, 1984, IEEE T COMPUT, V33, P323, DOI 10.1109/TC.1984.1676437

[4] Fault-tolerant cycle-embedding in alternating group graphs [J].

Chang, Jou-Ming ;

Yang, Jinn-Shyong .

APPLIED MATHEMATICS AND COMPUTATION, 2008, 197 (02) :760-767

[5] Controllability and Observability of Network-of-Networks via Cartesian Products [J].

Chapman, Airlie ;

Nabi-Abdolyousefi, Marzieh ;

Mesbahi, Mehran .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2014, 59 (10) :2668-2679

[6] PROCESSOR ALLOCATION IN AN N-CUBE MULTIPROCESSOR USING GRAY CODES [J].

CHEN, MS ;

SHIN, KG .

IEEE TRANSACTIONS ON COMPUTERS, 1987, 36 (12) :1396-1407

[7] Conditional Edge-Fault Hamiltonicity of Cartesian Product Graphs [J].

Cheng, Chia-Wen ;

Lee, Chia-Wei ;

Hsieh, Sun-Yuan .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2013, 24 (10) :1951-1960

[8] On connectivity of the Cartesian product of two graphs [J].

Chiue, WS ;

Shieh, BS .

APPLIED MATHEMATICS AND COMPUTATION, 1999, 102 (2-3) :129-137

[9] Minimal fault diameter for highly resilient product networks [J].

Day, K ;

Al-Ayyoub, AE .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2000, 11 (09) :926-930

[10] The cross product of interconnection networks [J].

Day, K ;

AlAyyoub, AE .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1997, 8 (02) :109-118

← 1 2 3 4 →