Structure and substructure connectivity of alternating group graphs

Highlights：

• The connectivity is an important indicator to evaluate the robustness of a network. Many works have focused on connectivity-based reliability analysis for decades. As a generalization of connectivity, H-structure connectivity and H-substructure connectivity were proposed to evaluate the robustness of networks. In the previous works, the H-structure connectivity and H-substructure connectivity for some classical networks have been done when H is isomorphic to K1, K1,1, K1,2. In this paper, we investigate the H-structure connectivity and H-substructure connectivity of alternating group graph AGn when H is isomorphic to K1,t, Pl, and Ck. And we show that (1) for a star K1, t (1≤t≤2n−6),k(AGn;K1,t)=ka(AGn;K1,t)=n−2; (2) for a path Pl (1≤l≤3n−7),κ(AGn;Pl)=κs(AGn;Pl)=⌈2n−4l−⌊l/3⌋⌉; (3) for a cycle Ck (6≤k≤3n−6),κs(AGn;Ck)=⌈2n−4k−⌊k/3⌋⌉andκ(AGn;Ck)=⌈n−2⌊k/3⌋⌉.

摘要

•The connectivity is an important indicator to evaluate the robustness of a network. Many works have focused on connectivity-based reliability analysis for decades. As a generalization of connectivity, H-structure connectivity and H-substructure connectivity were proposed to evaluate the robustness of networks. In the previous works, the H-structure connectivity and H-substructure connectivity for some classical networks have been done when H is isomorphic to K1, K1,1, K1,2. In this paper, we investigate the H-structure connectivity and H-substructure connectivity of alternating group graph AGn when H is isomorphic to K1,t, Pl, and Ck. And we show that (1) for a star K1, t (1≤t≤2n−6),k(AGn;K1,t)=ka(AGn;K1,t)=n−2; (2) for a path Pl (1≤l≤3n−7),κ(AGn;Pl)=κs(AGn;Pl)=⌈2n−4l−⌊l/3⌋⌉; (3) for a cycle Ck (6≤k≤3n−6),κs(AGn;Ck)=⌈2n−4k−⌊k/3⌋⌉andκ(AGn;Ck)=⌈n−2⌊k/3⌋⌉.

论文评审过程：Received 12 November 2019, Revised 8 May 2020, Accepted 22 August 2020, Available online 14 September 2020, Version of Record 14 September 2020.