JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19]


Journal of Information Science and Engineering, Vol. 25 No. 6, pp. 1855-1862


Fault-Tolerant Hamiltonian Connectivity and Fault-Tolerant Hamiltonicity of the Fully Connected Cubic Networks

TUNG-YANG HO AND CHENG-KUAN LIN*
Department of Information Management 
Ta Hwa Institute of Technology 
Hsinchu, 307 Taiwan 
E-mail: hoho@thit.edu.tw 
*Department of Computer Science 
National Chiao Tung University 
Hsinchu, 300 Taiwan

    Many papers on the fully connected cubic networks have been published for the past several years due to its favorite properties. In this paper, we consider the fault-tolerant hamiltonian connectivity and fault-tolerant hamiltonicity of the fully connected cubic network. We use FCCNn to denote the fully connected cubic network of level n. Let G = (V, E) be a graph. The fault-tolerant hamiltonian connectivity that Hkf(G) is defined to be the maximum integer l such that G - F remains hamiltonian connected for every F V(G) ∪ E(G) with |F| <= l. The fault-tolerant hamiltonicity Hf(G) is defined to be the maximum integer l such that G - F remains hamiltonian for every F V(G) ∪ E(G) with |F| <= l. We prove that Hkf(FCCNn) = 0 and Hf(FCCNn) = 1 if n = 2.

Keywords: hamiltonian, hamiltonian connected, fault-tolerant hamiltonian, fault-tolerant hamiltonian connected, fully connected cubic network

  Retrieve PDF document (JISE_200906_12.pdf)