Weak-quasi-bandwidth and forward-bandwidth of graphs (Q1919043)

Let \(G=(V,E)\) be a graph with \(|V|=n\) and \(\pi\) a labeling of \(G\), i.e. a bijection \(\pi:V\to \{1,\dots,n\}\). For a set \(S\subseteq V\) denote \(N(S)=\{u\in V-S\mid(\exists v\in S)(u,v)\in E\}\). Further denote \(S_k(G,\pi)=\{u\in V\mid 1\leq \pi(u)\leq k\}\), and define \(\widehat S_k(G,\pi)\) as the vertex set of the connected component of the induced subgraph \(G[S_k(G,\pi)]\) which contains \(\pi^{-1}(k)\). The author introduces the weak-quasi-bandwidth \(B_1(G)\) and forward-bandwidth \(B^*_1(G)\) by \(B_1(G)=\min_\pi\max_k|N(S_k(G,\pi)|\) and \(B^*_1(G)=\min_\pi\max_k|N(\widehat S_k(G,\pi))|\), respectively. He shows that for any graph \(G\) the tree-width and the path-width of \(G\) equal \(B_1(G)\) and \(B^*_1(G)\), respectively. The paper may be considered as a continuation of the author's research on bandwidth-like invariants of graphs such as the fill-in, the profile and the topological bandwidth. It contains a number of inequalities and equalities involving these and the above introduced invariants for general graphs and also some exact results for some special graph families.