Shannon multigraph

The Shannon multigraph or Shannon multigraph (after Claude Elwood Shannon ) denotes a special type of graph in graph theory , where they are particularly important in the theory of edge coloring.

A multigraph with three vertices, which are each connected to the same number of edges or which has one additional edge, is called a Shannon multigraph. More precisely, one speaks of the Shannon multigraph Sh (n) when the three vertices are connected by , and edges. ${\displaystyle \left\lfloor {\tfrac {n}{2}}\right\rfloor }$ ${\displaystyle \left\lfloor {\tfrac {n}{2}}\right\rfloor }$ ${\displaystyle \left\lfloor {\tfrac {n+1}{2}}\right\rfloor }$

For just now , the Shannon multigraph assumes the upper limit in Vizing's Theorem and in Shannon's Theorem and thus shows that these estimates are in a certain sense optimal. ${\displaystyle n}$

• Shannon multigraphs
• 

  ${\displaystyle Sh(2)}$

• 

  ${\displaystyle Sh(3)}$

• 

  ${\displaystyle Sh(4)}$

• 

  ${\displaystyle Sh(5)}$

• 

  ${\displaystyle Sh(6)}$

• 

  ${\displaystyle Sh(7)}$

literature

• Lutz Volkmann: Fundamente der Graphentheorie , Springer (Vienna) 1996, ISBN 3-211-82774-9 , p. 289

Web links

Commons : Shannon multigraphs  - collection of images, videos and audio files

• Lutz Volkmann: Graphs on all corners and edges (PDF; 3.7 MB) . Script 2006, p. 242