Shannon multigraph

Template:Short description In the mathematical discipline of graph theory, Shannon multigraphs, named after Claude Shannon by ,Template:R/superscript are a special type of triangle graphs, which are used in the field of edge coloring in particular.

A Shannon multigraph is multigraph with 3 vertices for which either of the following conditions holds:

• a) all 3 vertices are connected by the same number of edges.
• b) as in a) and one additional edge is added.

More precisely one speaks of Shannon multigraph Sh(n), if the three vertices are connected by $\lfloor \frac{n}{2}\rfloor$, $\lfloor \frac{n}{2}\rfloor$ and $\lfloor \frac{n+1}{2}\rfloor$ edges respectively. This multigraph has maximum degree Template:Mvar. Its multiplicity (the maximum number of edges in a set of edges that all have the same endpoints) is $\lfloor \frac{n+1}{2}\rfloor$.Template:R/superscriptTemplate:R/superscript

Examples

• Shannon multigraphs
• Sh(2)
  Sh(2)
• Sh(3)
  Sh(3)
• Sh(4)
  Sh(4)
• Sh(5)
  Sh(5)
• Sh(6)
  Sh(6)
• Sh(7)
  Sh(7)

Edge coloring

File:Multigraph-edge-coloring.svg

This nine-edge Shannon multigraph requires nine colors in any edge coloring; its vertex degree is six and its multiplicity is three.

According to a theorem of , every multigraph with maximum degree $\mathrm{\Delta }$ has an edge coloring that uses at most $\frac{3}{2}\mathrm{\Delta }$ colors.Template:R/superscript When $\mathrm{\Delta }$ is even, the example of the Shannon multigraph with multiplicity $\mathrm{\Delta }/2$ shows that this bound is tight: the vertex degree is exactly $\mathrm{\Delta }$, but each of the $\frac{3}{2}\mathrm{\Delta }$ edges is adjacent to every other edge, so it requires $\frac{3}{2}\mathrm{\Delta }$ colors in any proper edge coloring.Template:R/superscript

A version of Vizing's theorem states that every multigraph with maximum degree $\mathrm{\Delta }$ and multiplicity $\mu$ may be colored using at most $\mathrm{\Delta }+\mu$ colors.Template:R/superscript Again, this bound is tight for the Shannon multigraphs.Template:R/superscript

External links

• Lutz Volkmann: Graphen an allen Ecken und Kanten. Lecture notes 2006, p. 244 (German)