An extremal graph with given bandwidth

AbstractThe graph bandwidth problem is a well-known NP-complete problem. The relation between size of a graph and bandwidth is very interesting. The minimum size required in G with bandwidth B is denoted as m(n,B) while the graph G of order n and bandwidth B with size m(n,B) is called an extremal graph. This paper provides the minimum size for a graph of odd order n, n≥9, and bandwidth (n+1)/2, and shows that K2,n−2 is the only extremal graph of m(n,(n+1)/2)