Graph bandwidth: Difference between revisions

Revision as of 18:07, 18 January 2015

Revision as of 18:10, 18 January 2015

Line 22:

The bandwidth of a graph can be bounded in terms of various other graph parameters. For instance, letting χ(''G'') denote the [[chromatic number]] of ''G'',

:φ(''G'') ≥ χ(''G'') − 1;

: <math> \varphi(G) \le 20n /ge \log_\Deltachi(G) - n1; </math>.

letting diam(''G'') denote the [[diameter (graph theory)|diameter]] of ''G'', the following inequalities hold:<ref>{{harvnb|Chinn|Chvátalová|Dewdney|Gibbs|1982}}</ref>

:<math>\lceil (n-1)/\mathrmoperatorname{diam}(G) \rceil \le \varphi(G) \le n - \mathrmoperatorname{diam}(G)</math>,

where <math>n</math> is the number of vertices in <math>G</math>.

If a graph <math>''G</math>'' has bandwidth <math>''k</math>'', then its [[pathwidth]] is at most <math>''k</math>'' {{harv|Kaplan|Shamir|1996}}, and its [[tree-depth]] is at most <math>''k\''&nbsp;log(''n''/''k'')</math> {{harv|Gruber|2012}}. In contrast, as noted in the previous section, the star graph ''S''<mathsub>S_k''k''</mathsub>, a structurally very simple example of a [[tree (graph theory)|tree]], has comparatively large bandwidth. Observe that the [[pathwidth]] of ''S''_''k'' is&nbsp;1, and its tree-depth is&nbsp;2.

very simple example of a [[tree (graph theory)|tree]], has comparatively large bandwidth. Observe that the [[pathwidth]] of <math>S_k</math> is 1, and its tree-depth is 2.

Some graph families of bounded degree have sublinear bandwidth: {{harvtxt|Chung|1988}} proved that if ''T'' is a tree of maximum degree at most ''∆'', then

:<math>\varphi(T) \le \frac{5n / }{\log_\Delta n}. </math>.

Some graph families of bounded degree have sublinear bandwidth: {{harvtxt|Chung|1988}} proved that if ''T'' is a tree of maximum degree at most ''∆'', then

:<math>\varphi(T) \le 5n / \log_\Delta n</math>.

More generally, for [[planar graph]]s of bounded maximum degree at most ''∆'', a similar bound holds (cf. {{harvnb|Böttcher|Pruessmann|Taraz|Würfl|2010}}):

:<math>\varphi(G) \le 20n / \log_\Delta n </math>.

:<math>\varphi(G) \le \frac{20n}{\log_\Delta n}.</math>

==Computing the bandwidth==