Let G=(V,E)be a connected graph.For an integer h≥0,a subset F■V(G)(resp.F■E(G))of G,if any,is called an h-restricted vertex cut(resp.h-restricted edge cut)of G,if G-F is disconnected and every vertex in G-F has at ...Let G=(V,E)be a connected graph.For an integer h≥0,a subset F■V(G)(resp.F■E(G))of G,if any,is called an h-restricted vertex cut(resp.h-restricted edge cut)of G,if G-F is disconnected and every vertex in G-F has at least h neighbors.The cardinality of a minimum h-restricted vertex-cut(resp.h-restricted edge cut)of G is the h-restricted connectivity(resp.h-restricted edge connectivity)of G,and denoted by κ^(h)(G)(resp.λ^(h)(G)).The enhanced hypercube Q_(n,κ)(1≤k≤n)is a variant of the hypercube Q_(n).In this paper,we consider the h-restricted connectivity of Q_(n,κ) for 2≤k≤n-1.Our main results are as follows:(1)κ^(h)(Q_(n,κ))=2^(h)(n-h+1)for 4≤k≤n-1 and 0≤h≤n-3,λ^(h)(Q_(n,κ))=2^(h)(n-h+1)for 2≤k≤n-1 and 0≤h≤n-2.(2)κ^(h)(Q_(n,3))=2^(h-1)(n-h+1)for n≥5 and 4≤h≤n-1,κ^(h)(Q_(n,2))=2^(h-1)(n-h+1)for n≥4 and 3≤h≤n-1.(3)κ^(3)(Q_(n,3))=6n-16 for n≥5,κ^(2)(Q_(n,3))=4n-8 for n≥4 and κ^(2)(Q_(n,2))=3n-5 for n≥3,κ^(1)(Q_(n,3))=2n and κ^(3)(Q_(n,2))=2n-2 for n≥3.展开更多
文摘Let G=(V,E)be a connected graph.For an integer h≥0,a subset F■V(G)(resp.F■E(G))of G,if any,is called an h-restricted vertex cut(resp.h-restricted edge cut)of G,if G-F is disconnected and every vertex in G-F has at least h neighbors.The cardinality of a minimum h-restricted vertex-cut(resp.h-restricted edge cut)of G is the h-restricted connectivity(resp.h-restricted edge connectivity)of G,and denoted by κ^(h)(G)(resp.λ^(h)(G)).The enhanced hypercube Q_(n,κ)(1≤k≤n)is a variant of the hypercube Q_(n).In this paper,we consider the h-restricted connectivity of Q_(n,κ) for 2≤k≤n-1.Our main results are as follows:(1)κ^(h)(Q_(n,κ))=2^(h)(n-h+1)for 4≤k≤n-1 and 0≤h≤n-3,λ^(h)(Q_(n,κ))=2^(h)(n-h+1)for 2≤k≤n-1 and 0≤h≤n-2.(2)κ^(h)(Q_(n,3))=2^(h-1)(n-h+1)for n≥5 and 4≤h≤n-1,κ^(h)(Q_(n,2))=2^(h-1)(n-h+1)for n≥4 and 3≤h≤n-1.(3)κ^(3)(Q_(n,3))=6n-16 for n≥5,κ^(2)(Q_(n,3))=4n-8 for n≥4 and κ^(2)(Q_(n,2))=3n-5 for n≥3,κ^(1)(Q_(n,3))=2n and κ^(3)(Q_(n,2))=2n-2 for n≥3.
