Modern　large-scale　computing　systems　always　demand　better　connectivity　indicators　for　reliability　evaluation.　However,　as　more　processing　units　have　been　rapidly　incorporated　into　emerging　computing　systems,　existing　indicators　(e.g.,　-component　edge　connectivity　and　-extra　edge　connectivity)　have　gradually　failed　to　provide　the　required　fault　tolerance.　In　addition,　these　indicators　require,　for　example,　that　the　faulty　network　should　have　at　least　components　(or　that　each　component　should　have　at　least　nodes).　These　fault　assumptions　are　not　flexible　enough　to　deal　with　diversified　structural　demands　in　practice　circumstances.　In　order　to　address　these　challenges　simultaneously,　this　article　proposes　two　novel　indicators　for　network　reliability　by　utilizing　the　partition　matroid　technique,　named　matroidal　connectivity　and　conditional　matroidal　connectivity.　We　first　investigate　the　accurate　values　of　(conditional)　matroidal　connectivity　of　k　-ary　n　-cube　Qnk,　which　is　an　appealing　option　as　the　underlying　topology　for　modern　parallel　computing　systems.　Moreover,　we　propose　an　O(kn-1)　algorithm　for　determining　structural　features　of　minimum　edge　sets　whose　cardinality　is　the　conditional　matroidal　connectivity　of　Qnk.　Simulation　results　are　presented　to　verify　our　algorithm＇s　correctness　and　further　investigate　the　distribution　pattern　of　edge　sets　subject　to　the　restriction　of　partition　matroid.　We　also　present　comparative　analyses　illustrating　the　superior　edge　fault　tolerance　of　our　findings　in　relation　to　prior　research,　which　even　exhibits　an　exponential　enhancement　when　k　≥　4.　©　1963-2012　IEEE.