×

A bandwidth sum with an edge added. (Chinese. English summary) Zbl 1324.05174

Summary: Suppose \(f\) is a one-to-one mapping from \(V(G)\) onto \(\{1, 2,\dots,|V(G)|\}\). Let \(\mathrm{BS}(G, f)=\sum\limits_{uv\in E(G)}|f(u)-f(v)|\). The bandwidth sum of \(G\), denoted by \(\mathrm{BS}(G)\), is \(\mathrm{BS}(G)=\min\limits_{f}\mathrm{BS}(G, f)\). In this paper, we obtain the relationship between \(\mathrm{BS}(G+e)\) and \(\mathrm{BS}(G)\), where \(e\in\overline{E(G)}\), \(\mathrm{BS}(G)+1\leqslant \mathrm{BS}(G+e)\leqslant\mathrm{BS}(G)+n-1\). We also show that these bounds are sharp.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)