Find in Library

For an integer ℓ ≥ 2, the ℓ-component connectivity of a graph G, denoted by κ_ℓ(G), is the minimum number of vertices whose removal from G results in a disconnected graph with at least ℓ components or a graph with fewer than ℓ 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 ℓ-connectivity are known only for a few classes of networks and small ℓ's. It has been pointed out in component connectivity of the hypercubes, International Journal of Computer Mathematics 89 (2012) 137-145] that determining ℓ-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², we study their ℓ-component connectivities. We obtain the following results: 1) κ₃(AG_n) = 4n - 10 and κ₄(AG_n) = 6n - 16 for n ≥ 4, and κ₅(AG_n) = 8n - 24 for n ≥ 5 and 2) κ₃(S_n²) = 4n - 8, κ₄(S_n²) = 6n - 14, and κ₅(S_n²) = 8n - 20 for n ≥ 4.