Shannon Multigraph

In the mathematical discipline of graph theory, Shannon multigraphs, named after Claude Shannon by , 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 , if the three vertices are connected by $\left\lfloor \frac \right\rfloor$, $\left\lfloor \frac \right\rfloor$ and $\left\lfloor \frac \right\rfloor$ edges respectively. This multigraph has maximum degree . Its multiplicity (the maximum number of edges in a set of edges that all have the same endpoints) is $\left\lfloor \frac \right\rfloor$.

Examples

File:Shannon multigraph 2.svg, Sh(2)
File:Shannon multigraph 3.svg, Sh(3)
File:Shannon multigraph 4.svg, Sh(4)
File:Shannon multigraph 5.svg, Sh(5)
File:Shannon multigraph 6.svg, Sh(6)
File:Shannon multigraph 7.svg, Sh(7)

Edge coloring

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

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

References

*
*.
*.
*.
*.

External links

{{commons category, Shannon multigraphs
*Lutz Volkmann:
Graphen an allen Ecken und Kanten
'. Lecture notes 2006, p. 242 (German)

Parametric families of graphs