A lower bound for the vertex boundary-width of complete k-ary trees

The vertex boundary-width problem (for short VBWP) is to determine the value of vbw(G)=max1⩽ℓ⩽|V|minS⊆V,|S|=ℓ|N(S)|vbw(G)=max1⩽ℓ⩽|V|minS⊆V,|S|=ℓ|N(S)| for a given graph G=(V,E)G=(V,E), where N(S)={v∉S|vN(S)={v∉S|v is a neighbor of uu for some u∈S}u∈S}. In this paper, we give a lower bound for vertex boundary-width of complete k-ary trees.