Note on Edge-Colored Graphs for Networks with Homogeneous Faults

作者：Hou, Rui; Wu, Jigang^*; Chen, Yawen; Zhang, Haibo

来源：Computer Journal, 2016, 59(10): 1470-1478.

DOI：10.1093/comjnl/bxw012

• graphs
• network security
• network reliability
• Homogeneous faults
• fault tolerance

The failure on all homogeneous devices due to the same reason is called homogeneous fault in networks. In contrast, heterogeneous platforms deployed simultaneously in the network are more robust against homogeneous faults. One of the challenging problems is how to design survivable networks that against homogeneous faults. This paper utilizes edge-colored graphs to investigate the network topology with homogeneous faults, in order to guarantee network connectivity using minimum number of links. Two types of network topologies are proposed on the edge-colored graph. One type of networks is characterized by the fact that all the edges of the same color form a Hamiltonian path or a Hamiltonian cycle. An upper bound on the number of colors used in the proposed network topologies is obtained. The network topologies of the second type have edges colored with at most five colors. Additionally, the subnetworks induced by the edges of two colors contain a Hamiltonian path, or a Hamilton cycle in some cases.

• 出版日期2016-10
• 单位广东工业大学