Content deleted Content added
→See also: cutwidth |
Added chapter cyclically interval graphs |
||
Line 8:
In terms of matrices, the (unweighted) graph bandwidth is the minimal [[bandwidth (matrix theory)|bandwidth]] of a [[symmetric matrix]] which is an [[adjacency matrix]] of the graph.
The bandwidth may also be defined as one less than the [[maximum clique]] size in a [[proper interval graph|proper interval]] supergraph of the given graph, chosen to minimize its clique size {{harv|Kaplan|Shamir|1996}}.
==Cyclically interval graphs==
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.
Therefore, one 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 problem is known as
<b>topologic bandwidth</b>. An other graph measure related through the bandwidth is the
[[bisection bandwidth]].
==Bandwidth formulas for some graphs==
For several families of graphs, the bandwidth <math>\varphi(G)</math> is given by an explicit formula.
| |||