Graph bandwidth: Difference between revisions

Revision as of 18:13, 18 January 2015

Revision as of 18:14, 18 January 2015

Line 29:

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)/\operatorname{diam}(G) \rceil \le \varphi(G) \le n - \operatorname{diam}(G),</math>,

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