| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 438594 | Theoretical Computer Science | 2007 | 5 Pages |
Abstract
The 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).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
