Gráfico mágico

Un grafo mágico es un grafo cuyas aristas están etiquetadas con los primeros q enteros positivos , donde q es el número de aristas, de modo que la suma de las aristas incidentes a cualquier vértice es la misma, independientemente de la elección del vértice; o bien, es un grafo que posee dicha etiquetación. El término "mágico" a veces significa que los enteros son cualquier entero positivo; en ese caso, el grafo y la etiquetación que utiliza los primeros q enteros positivos se denominan supermágicos .

Un grafo es mágico en vértices si sus vértices pueden etiquetarse de tal manera que la suma de las etiquetas de cualquier arista sea la misma. Es mágico en su totalidad si sus aristas y vértices pueden etiquetarse de tal manera que la etiqueta del vértice más la suma de las etiquetas de las aristas incidentes a ese vértice sea una constante.

Existen numerosas variantes del concepto de etiquetado mágico de un gráfico. La terminología también varía considerablemente. Las definiciones que se presentan aquí son quizás las más comunes.

Las referencias exhaustivas sobre etiquetado mágico y gráficos mágicos son Gallian (1998), Wallis (2001) y Marr y Wallis (2013).

Un cuadrado semimágico es un cuadrado n × n con los números del 1 al ^n² en sus celdas, donde la suma de cada fila y columna es la misma. Un cuadrado semimágico es equivalente a una etiqueta mágica del grafo bipartito completo K _{n , n} . Los dos conjuntos de vértices de K _{n , n} corresponden a las filas y columnas del cuadrado, respectivamente, y la etiqueta en una arista r _i s _j es el valor en la fila i , columna j del cuadrado semimágico.

La definición de cuadrados semimágicos difiere de la de cuadrados mágicos en el tratamiento de las diagonales. Los cuadrados mágicos deben tener diagonales cuya suma sea igual a la suma de las filas y columnas, mientras que los cuadrados semimágicos no requieren esto. Por lo tanto, todo cuadrado mágico es semimágico, pero no a la inversa.

• Nora Hartsfield y Gerhard Ringel (1994, 2003), Perlas en la teoría de grafos , edición revisada. Dover Publications, Mineola, NY Sección 6.1.
• WD Wallis (2001), Magic Graphs . Birkhäuser Boston, Boston, Mass. ISBN 0-8176-4252-8
• Alison M. Marr y WD Wallis (2013), Magic Graphs . Segunda edición. Birkhäuser/Springer, Nueva York. ISBN 978-0-8176-8390-0; 978-0-8176-8391-7
• Joseph A. Gallian (1998), Un estudio dinámico del etiquetado de grafos. Electronic Journal of Combinatorics , vol. 5, Estudio dinámico 6. Actualizado muchas veces.