bandwidth

tags: vertex order

equivalent to: bandwidth

providers: ISGCI

Relations

Results

• 2019 The Graph Parameter Hierarchy by Sorge
  • page 10 : maximum leaf number upper bounds bandwidth by a linear function – Lemma 4.25. The max leaf number $\mathrm{ml}$ strictly upper bounds the bandwidth $\mathrm{bw}$.
• 1998 A partial $k$-arboretum of graphs with bounded treewidth by Bodlaender
  • page 22 : bandwidth – Let $G=(V,E)$ be a graph, and let $f\colon V\to {1,2,\dots,n}$ be a linear ordering of $G$. 1. The \emph{bandwidth} of $f$ is $\max{|f(v)-f(w)| \mid (v,w) \in E}$. … The bandwidth … is the minimum bandwidth … over all possible linear orderings of $G$.
  • page 23 : bandwidth upper bounds pathwidth by a linear function – Theorem 44. For every graph $G$, the pathwidth of $G$ is at most the bandwidth of $G$, … Proof. Let $f \colon V\to {1,\dots,n}$ be a linear ordering of $G$ with bandwidth $k$. Then $(X_1,\dots,X_{n-k})$ with $X_i={f^{-1}(i), f^{-1}(i+1), \dots, f^{-1}(i+k)}$ is a path decomposition of $G$ with pathwidth $k$. …
• Comparing Graph Parameters by Schröder
  • page 21 : bounded bandwidth does not imply bounded distance to planar – Proposition 3.13
  • page 26 : bounded bandwidth does not imply bounded distance to perfect – Proposition 3.24
  • page 30 : bounded bandwidth does not imply bounded genus – Proposition 3.27
• assumed
  • bandwidth upper bounds topological bandwidth by a linear function – By definition
• https://en.wikipedia.org/wiki/Graph_bandwidth
  • bandwidth – (paraphrased) Label graph vertices with distinct integers. Bandwidth of this labelling is the maximum over label differences over all edges. Bandwidth of a graph is the minimum over all labellings.
• unknown source
  • bandwidth upper bounds maximum degree by a linear function – Each vertex has an integer $i$ and may be connected only to vertices whose difference from $i$ is at most $k$. There are at most $k$ bigger and $k$ smaller such neighbors.
  • bandwidth upper and lower bounds cutwidth by a polynomial function – Any bandwidth bound cutwidth quadratically. An example where this happens is $(P_n)^k$ which has bandwidth $k$ and cutwidth $O(k^2)$; both seem to be optimal.