Conditional fault hamiltonian connectivity of the complete graph |
| |
Authors: | Tung-Yang Ho Yuan-Kang Shih Lih-Hsing Hsu |
| |
Affiliation: | a Department of Information Management, Ta Hwa Institute of Technology, Hsinchu, Taiwan 30740, ROC b Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan 30010, ROC c Department of Computer Science and Information Engineering, Providence University, Taichung, Taiwan 43301, ROC |
| |
Abstract: | A path in G is a hamiltonian path if it contains all vertices of G. A graph G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices of G. The degree of a vertex u in G is the number of vertices of G adjacent to u. We denote by δ(G) the minimum degree of vertices of G. A graph G is conditional k edge-fault tolerant hamiltonian connected if G−F is hamiltonian connected for every F⊂E(G) with |F|?k and δ(G−F)?3. The conditional edge-fault tolerant hamiltonian connectivity is defined as the maximum integer k such that G is k edge-fault tolerant conditional hamiltonian connected if G is hamiltonian connected and is undefined otherwise. Let n?4. We use Kn to denote the complete graph with n vertices. In this paper, we show that for n∉{4,5,8,10}, , , , and . |
| |
Keywords: | Complete graph Hamiltonian Hamiltonian connected Fault tolerance |
本文献已被 ScienceDirect 等数据库收录! |
|