Super Connectivity of Star Graphs, Alternating Group Graphs and Split-Stars

The star graph \(S_n\) and the alternating group graph \(A_n\) are two popular interconnection graph topologies. \(A_n\) has a higher connectivity while \(S_n\) has a lower degree, and the choice between the two graphs depends on the specific requirement of an application. The degree of \(S_n\) can be even or odd, but the degree of \(A_n\) is always even. We present a new interconnection graph topology, split-star graph \(S^2_{n}\), whose degree is always odd. \(S^2_{n}\) contains two copies of \(A_n\) and can be viewed as a companion graph for \(A_n\). We demonstrate that this graph satisfies all the basic properties required for a good interconnection graph topology. In this paper, we also evaluate \(S_n\), \(A_n\), and \(S^2_{n}\) with respect to the notion of super connectivity and super edge-connectivity.