Cyclic bandwidth with an edge added (Q2462360)

Let \(\mathcal B_c(G)\) denote the cyclic bandwidth of a graph \(G\). The authors give the maximum cyclic bandwidth of graphs of order \(p\) by adding an edge \(e\), as follows: \[ \mathcal B_c(G + e) = \begin{cases} 2\mathcal B_c(G) & \text{if } \mathcal B_c(G)\leq \frac{p}{8}\\ \left\lceil \frac{1}{3}\left(\left\lfloor \frac{p}{2}\right\rfloor + 2\mathcal B_c(G) \right)\right\rceil & \text{if }\mathcal B_c(G) > \frac{5}{8}. \end{cases} \] It is shown that this bound is sharp.