Component Connectivity of Alternating Group Networks and Godan Graphs

Hong Zhang, Shuming Zhou, Qifan Zhang

2022International Journal of Foundations of Computer Science18 citationsDOI

Abstract

Connectivity is an important index to evaluate the reliability and fault tolerance of a graph. As a natural extension of the connectivity of graphs, the [Formula: see text]-component connectivity of a graph [Formula: see text], denoted by [Formula: see text], is the minimum number of vertices whose removal from [Formula: see text] results in a disconnected graph with at least [Formula: see text] components. It is a scientific issue to determine the exact values of [Formula: see text] for distinguishing the fault tolerability of networks. However, [Formula: see text]-component connectivity of many well-known interconnection networks has not been explored even for small [Formula: see text]. For the [Formula: see text]-dimensional alternating group networks [Formula: see text] and [Formula: see text]-dimensional godan graphs [Formula: see text], we show that [Formula: see text] for [Formula: see text], and [Formula: see text] for [Formula: see text] and [Formula: see text].

Topics & Concepts

Connected componentCombinatoricsMathematicsGraphDiscrete mathematicsComputer scienceInterconnection Networks and SystemsGraph theory and applicationsSoftware-Defined Networks and 5G