On the problem of bandsize (Q1089353): Difference between revisions

A vertex-numbering of an undirected graph G with N vertices is a bijection f of the vertex set of G onto the number set \(\{\) 1,2,...,N\(\}\). If \(\{\) v,w\(\}\) is an edge of G, then the number \(| f(v)-f(w)|\) is called an edge-differences of f. The bandsize of G, denoted by bs(G), is the minimum number of distinct edge-differences, taken over all vertex-numberings of G. The bandsize is compared with the radius of the graph. For the complete binary tree \(T_ n\) of height n the inequality \(n/7<bs(T_ n)<4n/5+2\) is presented.