國立臺灣大學資訊工程學系Hsieh, Sun-YuanSun-YuanHsiehChen, Gen-HueyGen-HueyChenHo, Chin-WenChin-WenHo2006-09-272018-07-052006-09-272018-07-051999-12-07http://ntur.lib.ntu.edu.tw//handle/246246/20060927122918898556In this paper, we aim to embed a longest path between every two vertices of a star graph with at most n-3 random edge faults, where n is the dimension of the star graph. Since the star graph is regular of degree n-1, n-3 (edge faults) is maximum in the worst case. We show that when n摯瑬敳獩 6 and there are n-3 edge faults, the star graph can embed a longest path between every two vertices, exclusive of two exceptions in which there are at most two vertices missing from the longest path. The probabilities of the two exceptions are analyzed. When n摯瑬敳獩 6 and there are n-4 edge faults, the star graph can embed a longest path between every two vertices. The situation of n<6 is also discussed.application/pdf273216 bytesapplication/pdfzh-TWembeddingfault-tolerant embeddinghamiltonian pathlongest pathstar graphreporthttp://ntur.lib.ntu.edu.tw/bitstream/246246/20060927122918898556/1/star-99-04.pdf