---
tag: R9ASE0ZW4T
kind: concept
name: Bandwidth
sources:
  - wikipedia: en:325802@r1373839425
    locator: Glossary of graph theory, section B
    note: adopted
    mention: wikipedia://en/325802#TNXG
    sections: [Summary]
inventory: [3W48Q4WDT0]
---

## Summary

The bandwidth of a graph $G$ is the minimum, over all orderings of vertices of $G$, of the length of the longest edge (the number of steps in the ordering between its two endpoints). It is also one less than the size of the maximum clique in a proper interval completion of $G$, chosen to minimize the clique size.