Reliability Evaluation of Star Graphs in Terms of Extra Edge Connectivity
Ming-Chien Yang · 2016
The g-extra edge connectivity is a novel measure of the reliability of an interconnection network. In this paper, we study the {2, 3}-extra edge connectivity of the star graph Sn. We show that λg(Sn) = (g+1)n-3g-1 for g = 2, 3 and n ≥ 4. This means that, to become a disconnected graph with every component having more than g vertices, we need to delete at least (g+1)n-3g-1 edges from Sn for g = 2, 3 and n ≥ 4. We also remark that the equation λg(Sn) = (g+1)n-3g-1 does not hold for g = 4.