No label defined (Q4518334)

An edge-labeling of a graph \(G\) is an injection from \(E_G\) to the set of integers. The edge-bandwidth \(B'(G)\) is the maximum difference between labels of incident edges. The authors study the edge-bandwidth of theta graphs \(\Theta(l_1,\dots,l_m)\) consisting of \(m\) pairwise internally disjoint paths with common endpoints and lengths \(l_1\leq\cdots\leq l_m\). These graphs are also interesting from the viewpoint of the usual bandwidth because standard lower bounds for both parameters are not tight. The main result is the formula \(B'(\Theta(l_1,\dots,l_m)) = \lceil(3m - 2 -U(G))/2\rceil\), where \(U(G)\) is the largest integer \(u\) such that \[ (l_1-1)(3m-2-u)/2\geq \sum_{c+1}^u (l_i-2) + (l_1-1)(m-u+c), \] and \(c=\max\{i: l_i=l_1\}\).