Shannon multigraph

In the mathematical discipline of graph theory, Shannon multigraphs, named after Claude Shannon by {{harvtxt|Vizing|1965}}, 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 $\left\lfloor \frac{n}{2} \right\rfloor$ , $\left\lfloor \frac{n}{2} \right\rfloor$ and $\left\lfloor \frac{n+1}{2} \right\rfloor$ 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 $\left\lfloor \frac{n+1}{2} \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

File:Multigraph-edge-coloring.svg

According to a theorem of {{harvtxt|Shannon|1949}}, 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 {{harv|Vizing|1964}} 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

{{citation

| last1 = Fiorini | first1 = S.

| last2 = Wilson | first2 = Robin James

| 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}}

{{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}}.

{{citation|first=Lutz|last=Volkmann|title=Fundamente der Graphentheorie|language=German|publisher=Springer|location=Wien|year=1996|isbn=3-211-82774-9|page=289}}.
{{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}}.

{{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}}.

External links

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. 242 (German)

Category:Parametric families of graphs