Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth

The neighbourhood complexity $nc(G,k)$ of a graph $G$ is a quantity measuring, for a graph $G$ and an integer $k$, the maximum possible number (over all vertex subsets $S$ of size $k$) $\mathrm{\mid }\{N[v]\cap S,v\in V(G)\}\mathrm{\mid }$ of $S$-neighbourhoods in $G$. This notion is important in structural graph theory and algorithm design (especially in parameterized complexity, in particular model checking and kernelization). While generally $nc(G,k)\le 2^k$ and this bound can be achieved, it is known that sparse graphs and structured dense graphs have linear neighbourhood complexity, that is, $nc(G,k)\in O(k)$ for any such graph $G$. However, for many graph classes, the best possible constants are not known. We focus on graphs of bounded treewidth and pathwidth, showing that (when $k\ge w+1$) (i) if $G$ has treewidth $w\ge 2$, then $nc(G,k)\le (k-w+1)2^w+w$, and (ii) if $G$ has pathwidth $w\ge 2$, then $nc(G,k)\le (k-w+2)2^{w-1}+2k-w-2$. Moreover, we provide constructions that reach these bounds, whenever $w\ge 2$ and $k\ge 2w+1$ ($k\ge 2w-1$ for pathwidth). Interestingly, in contrast, we also have the tight bound $nc(G,k)\le \frac{7}{3}k$, for graphs $G$ with pathwidth 1 or treewidth 1.