 Graph bandwidth

For a finite graph $G$ on $n$ vertices, its graph bandwidth is the minimum of ${\max }_{uv\in E}|\ell (u)-\ell (v)|$ over all bijective labels $\ell :V\to \{1,\dots ,n\}$. It asks how close adjacent vertices can be placed in a line. For an edgeless graph the bandwidth is taken as zero.

A path has bandwidth one, while a complete graph has bandwidth $n-1$. With the same ordering of rows and columns, this is the smallest matrix bandwidth achievable for the adjacency matrix. It matters in storing sparse matrices and reducing the work or memory associated with interactions far from the diagonal.

Graph bandwidth is a measure of how "spread out" the vertices of a graph are when it is represented in a certain way, particularly in terms of the adjacency matrix of the graph. Specifically, for a given graph \( G \) with vertex set \( V \), if we arrange the vertices in a specific order or permutation, the bandwidth is defined as the maximum distance between any two vertices that are connected by an edge in that arrangement.