= 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,\ldots,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.
Back to article page
