.png){kind=icon}
.png){kind=icon}
Return
On the d-blocker number of k-ary n-cubes
.png){kind=icon}
PRE
AI
H
H
DOI：10.1016/j.amc.2026.130219.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Consider a graph G with matching number ν(G). For an integer d with 1 ≤ d ≤ ν(G), a set B⊆E(G) is a d-blocker if removing all edges of B from G yields a subgraph G−B satisfying ν(G−B)≤ν(G)−d . The d-blocker number βd(G) is the smallest size of a d-blocker set of G. Given any d ≥ 1, computing the d-blocker number in a bipartite graph is NP-complete. In this paper, we investigate the d-blocker number of k-ary n-cube Qnk , a structure derived from the hypercube Qn. We first establish that the 4-restricted edge connectivity of Qn3 equals 8n−8 for n ≥ 2. Using properties of cyclic edge-connectivity and s-restricted edge connectivity of Qnk , and the concept of maximal barriers in graphs, we derive that β2(Qnk)=8n−4 for n ≥ 2, odd k ≥ 3 with kn−1≥7 , and βd(Qnk)=2nd+n for n ≥ 2, odd k ≥ 3 and kn−1−12≤d≤kn−12 .
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W
Organization
No organization information available
Cited Papers