A lower bound for the vertex boundary-width of complete \(k\)-ary trees (Q2427498): Difference between revisions

For a set \(S\) of vertices of a graph, \(N(S)=\{v\notin S| v\) is a neighbour of \(u\) for some \(u\in S\}\); \(T(k,d)\) denotes the complete \(k\)-ary tree in which all non-leaves have \(k\) children, and all leaves have distance \(d\) from the root. The vertex boundary-width problem (VBWP) is to determine, for a graph \(G=(V,E)\), \(\text{vbw}(G)=\max_{1\leq\ell\leq| V| }\min_{S\subseteq V,| S| =\ell}| N(S)| \). Theorem~1. \(\text{vbw}(T(k,d))\geq\frac{d\log k-(k+6+2\log d)}{k+6+2\log d}\).