Conditional fault-tolerant hamiltonicity of star graphs |
| |
| Affiliation: | 1. School of Mathematics and Computer Science, Fujian Normal University, Fuzhou, Fujian, 350007, PR China;2. Fujian Provincial Key Laboratory of Network Security and Cryptology (Fujian Normal University), Fujian Normal University, Fuzhou, Fujian, 350108, PR China;3. Department of Computer Science, Montclair State University, Upper Montclair, NJ 07043, USA;1. School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 610054, PR China;2. School of Sciences, Nanchang University, Nanchang, Jiangxi 330000, PR China;1. School of Information Science and Engineering, Lanzhou University, Lanzhou, Gansu 730000, PR China;2. School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu 730000, PR China;1. School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007, PR China;2. Henan Engineering Laboratory for Big Data and Statistical Analysis and Optimal Control, Henan Normal University, Xinxiang, Henan 453007, PR China;3. School of Applied Science, Taiyuan University of Science and Technology, Taiyuan, Shanxi 030024, PR China;1. School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007, PR China;2. Henan Engineering Laboratory for Big Data and Statistical Analysis and Optimal Control, Henan Normal University, Xinxiang, Henan 453007, PR China |
| |
| Abstract: | The star graph possesses many nice topological properties. In this study, we show that for any n-dimensional star graph (n ? 4) with ?2n ? 7 edge faults in which each node is incident to at least two non-faulty edges, there exists a fault-free Hamiltonian cycle. Compared with the corresponding study in hypercube, our method is rather succinct. Additionally, we also show the probability that an n dimensional star graph with arbitrary 2n ? 7 faulty edges at most is Hamiltonian is very close to one. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
