Measuring the Vulnerability of Alternating Group Graphs and Split-Star Networks in Terms of Component Connectivity
Abstract
For an integer l >= 2, the l-component connectivity of a graph G, denoted by kappa(l)(G), is the minimum number of vertices whose removal from G results in a disconnected graph with at least l components or a graph with fewer than l vertices. This is a natural generalization of the classical connectivity of graphs defined in term of the minimum vertex-cut and a good measure of vulnerability for the graph corresponding to a network.
So far, the exact values of l-connectivity are known only for a few classes of networks and small l's. It has been pointed out in component connectivity of the hypercubes, International Journal of Computer Mathematics 89 (2012) 137-145] that determining l-connectivity is still unsolved for most interconnection networks such as alternating group graphs and star graphs.
In this paper, by exploring the combinatorial properties and the fault-tolerance of the alternating group graphs AG(n) and a variation of the star graphs called split-stars S-n(2), we study their l-component connectivities. We obtain the following results: 1) kappa(3)(AG(n)) = 4n - 10 and kappa(4)(AG(n)) = 6n - 16 for n >= 4, and kappa(5)(AG(n)) = 8n - 24 for n >= 5 and 2) kappa(3)(S-n(2)) = 4n - 8, kappa(4)(S-n(2)) = 6n - 14, and kappa(5)(S-n(2)) = 8n - 20 for n >= 4.