Longest paths and cycles in faulty star graphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Longest paths and cycles in faulty star graphs

Affiliation:	1. School of Computer Science and Information Engineering, The Catholic University of Korea, San. 43-1, Yokkok 2-Dong, Wonmi-Gu, Puchon City 420-743, Republic of Korea;2. Computer Science and Information Communications Engineering Division, Hankuk University of Foreign Studies, Republic of Korea;1. School of Computer Science and Technology, Soochow University, Suzhou 215006, China;2. Provincial Key Laboratory for Computer Information Processing Technology, Soochow University, China;1. Department of Tourism Management, Ta Hwa University of Science and Technology, Hsinchu 30740, Taiwan, ROC;2. School of Computer Science and Technology, Soochow University, Suzhou 215006, China;3. Department of Computer Science, National Chiao Tung University, Hsinchu 30010, Taiwan, ROC;4. Department of Computer Science and Information Engineering, Providence University, Taichung 43301, Taiwan, ROC;1. School of Computer Science and Technology, Soochow University, Suzhou 215006, China;2. Department of Computer Science and Information Engineering, Providence University, Taichung 433, Taiwan;3. Department of Computer Science and Information Engineering, Asia University, Taichung 413, Taiwan;4. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China;1. Department of Computer and Web Information Engineering, Hankyong National University, Anseong, Republic of Korea;2. School of Computer Science and Information Engineering, The Catholic University of Korea, Bucheon, Republic of Korea

Abstract:	In this paper, we investigate the star graph $S_{n}$ with faulty vertices and/or edges from the graph theoretic point of view. We show that between every pair of vertices with different colors in a bicoloring of $S_{n}$ , $n ? 4$ , there is a fault-free path of length at least $n! - 2 f_{v} - 1$ , and there is a path of length at least $n! - 2 f_{v} - 2$ joining a pair of vertices with the same color, when the number of faulty elements is $n - 3$ or less. Here, $f_{v}$ is the number of faulty vertices. $S_{n}$ , $n ? 4$ , with at most $n - 2$ faulty elements has a fault-free cycle of length at least $n! - 2 f_{v}$ unless the number of faulty elements are $n - 2$ and all the faulty elements are edges incident to a common vertex. It is also shown that $S_{n}$ , $n ? 4$ , is strongly hamiltonian-laceable if the number of faulty elements is $n - 3$ or less and the number of faulty vertices is one or less.

Keywords:
本文献已被 ScienceDirect 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏