Multigrafía de Shannon

En la disciplina matemática de la teoría de grafos , los multigrafos de Shannon , nombrados en honor a Claude Shannon por Vizing (1965) , ^{[ 1 ]} son ​​un tipo especial de grafos triangulares , que se utilizan en el campo de la coloración de aristas en particular.

Un multigrafo de Shannon es un multigrafo con 3 vértices para el cual se cumple alguna de las siguientes condiciones:

• a) Los 3 vértices están conectados por el mismo número de aristas.
• b) igual que en a) y se añade una arista adicional.

Más precisamente se habla de multigrafo de Shannon Sh( n ) , si los tres vértices están conectados por${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }$,${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }$y${\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }$aristas respectivamente. Este multigrafo tiene un grado máximo n . Su multiplicidad (el número máximo de aristas en un conjunto de aristas que tienen todos los mismos puntos finales) es${\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }$. ^{[ 2 ] [ 3 ]}

• Multigrafías de Shannon
• 
  Sh(2)
• 
  Sh(3)
• 
  Sh(4)
• 
  Sh(5)
• 
  Sh(6)
• 
  Sh(7)

Según un teorema de Shannon (1949) , todo multigrafo con grado máximo${\displaystyle \Delta }$tiene un color de borde que utiliza como máximo${\displaystyle {\frac {3}{2}}\Delta}$colores. ^{[ 4 ]} Cuando${\displaystyle \Delta }$es incluso, el ejemplo del multigrafo de Shannon con multiplicidad${\displaystyle \Delta /2}$muestra que esta cota es ajustada: el grado del vértice es exactamente${\displaystyle \Delta }$, pero cada uno de los${\displaystyle {\frac {3}{2}}\Delta}$los bordes son adyacentes a todos los demás bordes, por lo que requiere${\displaystyle {\frac {3}{2}}\Delta}$colores en cualquier coloración de borde adecuada. ^{[ 3 ]}

Una versión del teorema de Vizing establece que todo multigrafo con grado máximo${\displaystyle \Delta }$y multiplicidad${\displaystyle \mu }$puede colorearse usando como máximo${\displaystyle \Delta +\mu }$colores. ^{[ 5 ]} Nuevamente, este límite es ajustado para los multigrafos de Shannon. ^{[ 3 ]}

• Lutz Volkmann: Graphen an allen Ecken und Kanten . Notas de conferencias de 2006, pág.  244 (alemán)