Previous [ 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 (November 2009)

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

Full Text () Retrieve PDF document (200911_12.pdf)

Received December 5, 2007; revised March 18, 2008; accepted April 17, 2008.
Communicated by Ding-Zhu Du.