The cutwidth of trees with diameters at most 4 (Q1430969)

The cutwidth of a permutation of the vertices of a graph \(G=(V,E)\) is the maximum over all vertices \(v\) of the number of edges \(\{x,y\}\) with \(x\) equal to \(v\) or before \(v\) in the permutation, and \(y\) after \(v\) in the permutation. The cutwidth of a graph is the minimum cutwidth over all permutations of its vertices. Cutwidth is NP-complete, but polynomial time computable when the graph is a tree. This paper gives an exact formula for trees whose diameter is at most four. Also, it is shown that for trees with diameter at most four, the cutwidth is at most the bandwidth.