Graph bandwidth: Difference between revisions

Revision as of 19:55, 12 October 2024

Revision as of 14:56, 17 October 2024

Line 13:

For fixed <math>k</math> define for every <math>i</math> the set

<math>I_k(i) := [i, i+k+1)</math>. <math>G_k(n)</math> is the corresponding interval graph formed from

the intervals <math>I_k(1), I_k(2), ... I_k(n)</math>. These are <b>'''exactly</b>''' the proper interval

graphs of graphs having bandwidth <math>k</math>. These graphs called be

<b>'''cyclically interval graphs</b>''' because the intervals can be assigned to layers

<math>L_1, L_2, ... L_{k+1}</math> in cyclically order, where the intervals of a layer doesn't

intersect.

Line 24:

Alternate adding vertices on edges can decrease the bandwidth. Hint: The last problem is known as

<b>'''topologic bandwidth</b>'''. An other graph measure related through the bandwidth is the

[[bisection bandwidth]].