No label defined (Q3837151)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1382527
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1382527 |
Statements
3 August 2000
0 references
Morgan-Scott graph
0 references
bandwidth
0 references
line graph
0 references
belt-length
0 references
The Morgan-Scott graph \(G(k, s)\) is the graph obtained by taking a cycle with \(s\) vertices and adding to each vertex of the cycle \(k-1\) edges to a vertex of degree one. The bandwidth of a graph \(G\) is the minimum over all bijections \[ f:V_G\to \{1,2,\dots,|V_G|\}\text{ of }\max\{|f(v)-f(w)|:\{v,w\}\in E_G\}. \] This paper establishes precise bounds for the bandwidth of the line graphs of Morgan-Scott graphs. The bandwidth of the line graph of \(G\) is also called the belt-length of \(G\).
0 references
