Embed a Longest Path between Arbitrary Two Vertices of a Faulty Star Graph
Date Issued
2000-01
Date
2000-01
Author(s)
DOI
20060927122911257271
Abstract
The star graph Sn has been recognized as an attractive alternative to the hypercube. Since S1, S2, & S3 have trivial structures, we focus our attention on Sn with n≥4 in this paper. Let Fv denote the set of faulty vertices in Sn. We show that when |Fv|≤n−5, Sn with n≥6 can embed a fault−free path of length n!-2|Fv|−2 (n!-2|Fv|−1, respectively) between arbitrary two vertices of even (odd, respectively) distance.
Publisher
臺北市:國立臺灣大學資訊工程學系
Type
report
File(s)![Thumbnail Image]()
Loading...
Name
star-00-01.pdf
Size
154.47 KB
Format
Adobe PDF
Checksum
(MD5):9515aa03f83f6061750fe081c3f93ce3