{{Short description|Three-vertex regular multigraph}} In the mathematical discipline of graph theory, '''Shannon multigraphs''', named after Claude Shannon by {{harvtxt|Vizing|1965}},{{r|v65}} 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 {{math|Sh(''n'')}}, if the three vertices are connected by <math>\left\lfloor \frac{n}{2} \right\rfloor </math>, <math>\left\lfloor \frac{n}{2} \right\rfloor </math> and <math>\left\lfloor \frac{n+1}{2} \right\rfloor </math> edges respectively. This multigraph has maximum degree {{mvar|n}}. Its multiplicity (the maximum number of edges in a set of edges that all have the same endpoints) is <math>\left\lfloor \frac{n+1}{2} \right\rfloor </math>.{{r|fw77|v96}}
==Examples== <gallery widths="100" heights="100" perrow="7" caption="Shannon multigraphs"> 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) </gallery>
==Edge coloring== thumb|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 {{harvtxt|Shannon|1949}}, every multigraph with maximum degree <math>\Delta</math> has an edge coloring that uses at most <math>\frac32\Delta</math> colors.{{r|s49}} When <math>\Delta</math> is even, the example of the Shannon multigraph with multiplicity <math>\Delta/2</math> shows that this bound is tight: the vertex degree is exactly <math>\Delta</math>, but each of the <math>\frac32\Delta</math> edges is adjacent to every other edge, so it requires <math>\frac32\Delta</math> colors in any proper edge coloring.{{r|v96}}
A version of Vizing's theorem states that every multigraph with maximum degree <math>\Delta</math> and multiplicity <math>\mu</math> may be colored using at most <math>\Delta+\mu</math> colors.{{r|v64}} Again, this bound is tight for the Shannon multigraphs.{{r|v96}}
==References== <references>
<ref name=fw77>{{citation | last1 = Fiorini | first1 = S. | last2 = Wilson | first2 = Robin James |author-link2=Robin Wilson (mathematician) | isbn = 0-273-01129-4 | location = London | mr = 0543798 | page = 34 | publisher = Pitman | series = Research Notes in Mathematics | title = Edge-colourings of graphs | volume = 16 | year = 1977}}</ref>
<ref name=s49>{{citation | last = Shannon | first = Claude E. | authorlink = Claude Shannon | title = A theorem on coloring the lines of a network | mr = 0030203 | doi = 10.1002/sapm1949281148 | journal = J. Math. Physics | volume = 28 | year = 1949 | pages = 148–151| hdl = 10338.dmlcz/101098| hdl-access = free}}</ref>
<ref name=v96>{{citation|first=Lutz|last=Volkmann|title=Fundamente der Graphentheorie|language=German|publisher=Springer|location=Wien|year=1996|isbn=3-211-82774-9|page=289}}</ref>
<ref name=v64>{{citation | last = Vizing | first = V. G. | year = 1964 | authorlink = Vadim G. Vizing | title = On an estimate of the chromatic class of a ''p''-graph | mr = 0180505 | journal = Diskret. Analiz. | volume = 3 | pages = 25–30}}</ref>
<ref name=v65>{{citation | last = Vizing | first = V. G. | issue = 3 | journal = Kibernetika | mr = 0189915 | pages = 29–39 | title = The chromatic class of a multigraph | volume = 1965 | year = 1965}}</ref>
</references>
==External links== {{commons category|Shannon multigraphs}} *Lutz Volkmann: ''[http://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf Graphen an allen Ecken und Kanten]''. Lecture notes 2006, p. 244 (German)
Category:Parametric families of graphs