On the extraconnectivity of k-ary n-cube networks

ABSTRACT

Given a graph G and a non-negative integer g, the g-extraconnectivity of G is the cardinality of a minimum set of vertices in G, if such a set exists, whose deletion disconnects G and leaves every remaining component with more than g vertices. The 2-extraconnectivity of k-ary n-cubes is gotten by Hsieh and Chang [Extraconnectivity of k-ary n-cube networks. Theoret. Comput. Sci. 443 (2012) 63–69] for $k\ge 4$. This paper shows that the 3-extraconnectivity of the k-ary n-cubes is $8n-9$, where $n\ge 3$ and $k\ge 4$.

KEYWORDS:

• Interconnection network
• k-ary n-cube
• fault tolerance
• extraconnectivity

2010 AMS SUBJECT CLASSIFICATIONS:

• 05C40
• 05C90

Acknowledgements

The authors would like to thank the editor and the anonymous reviewers for their valuable and kind suggestions which greatly improved the original manuscript.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [Grant No. 11371052, 11271012, 11171020].