scientific article; zbMATH DE number 1533071
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\}\).
- Bandwidth of theta graphs with short paths
- New results on edge-bandwidth
- scientific article; zbMATH DE number 4063151 (Why is no real title available?)
- Edge-Bandwidth of Graphs
- New bounds on the edge-bandwidth of triangular grids
- The extremal function for two disjoint cycles
- Edge-bandwidth of grids and tori
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4518334)
