The bandwidth of the complement of a \(k\)-tree (Q1288223)

For an integer \(k\) define recursively a \(k\)-tree \(T\) on \(n\geq k\) vertices. If \(n=k\) then set \(T=K_k\). Now for \(n\geq k\) construct a \(k\)-tree \(T\) on \(n+1\) vertices by taking a \(k\)-tree \(T'\) on \(n\) vertices, and joining a new vertex with a clique of size \(k\) in \(T'\). The paper deals with the bandwidth problem for the complement of a \(k\)-tree. It is known that the bandwidth problem is NP-complete even for trees (\(k=1\)), and, thus, for \(k\)-trees. However, the bandwidth of the complement \(\overline T\) of a \(k\)-tree \(T\) can be precisely computed: \[ B(\overline T)=\begin{cases} n-k-1, &\text{if } T\cong K_k+\overline K_{n-k}\\ n-k-2, &\text{otherwise.}\end{cases} \] The lower bound is based on an isoperimetric approach. The upper bound is done essentially by induction by tedious consideration of several cases.