Graph bandwidth: Difference between revisions

Revision as of 06:10, 1 August 2024

Latest revision as of 17:50, 2 July 2025

(3 intermediate revisions by 2 users not shown)

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 calledare becalled

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

<math>L_1, L_2, ... L_{k+1}</math> in cyclicallycyclical order, wheresuch that the intervals of a layer doesndon't

intersect.

Therefore, one can see the relation to the [[pathwidth]]. Pathwidth restricted graphs are minor closed but

the set of subgraphs of cyclically interval graphs are not. This follows from the fact, that thrinking

degree 2 vertices may increase the bandwidth.

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

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

[[bisection bandwidth]].