Un gráfico mágico es un gráfico cuyas aristas están etiquetadas por los primeros q enteros positivos, donde q es el número de aristas, de modo que la suma de las aristas incidentes con cualquier vértice es la misma, independientemente de la elección del vértice; o es un gráfico que tiene ese etiquetado. El nombre "mágico" a veces significa que los números enteros son números enteros positivos; entonces el gráfico y el etiquetado utilizando los primeros q enteros positivos se denominan supermagia .
Un gráfico es mágico de vértices si sus vértices se pueden etiquetar de modo que la suma en cualquier borde sea la misma. Es magia total si sus bordes y vértices se pueden etiquetar de modo que la etiqueta del vértice más la suma de las etiquetas en los bordes incidentes con ese vértice sea una constante.
Hay muchas variaciones en el concepto de etiquetado mágico de un gráfico. También hay mucha variación en la terminología. Las definiciones aquí son quizás las más comunes.
Las referencias completas para las etiquetas mágicas y los gráficos mágicos son Gallian (1998), Wallis (2001) y Marr y Wallis (2013).
Cuadrados magicos
Un cuadrado semimagic es un n × n cuadrado con los números 1 a n 2 en sus células, en los que la suma de cada fila y columna es el mismo. Un cuadrado semimagico es equivalente a un etiquetado mágico 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 un borde r i s j es el valor en la fila i , columna j del cuadrado semimagico.
La definición de cuadrados semimágicos difiere de la definición de cuadrados mágicos en el tratamiento de las diagonales del cuadrado. Se requiere que los cuadrados mágicos tengan diagonales con la misma suma que las sumas de filas y columnas, pero para los cuadrados semimágicos esto no es necesario. Por tanto, todo cuadrado mágico es semimagico, pero no al revés.
Referencias
- Nora Hartsfield y Gerhard Ringel (1994, 2003), Pearls in Graph Theory , edición revisada. Publicaciones de Dover, Mineola, NY Sección 6.1.
- WD Wallis (2001), Gráficos mágicos . Birkhäuser Boston, Boston, Mass. ISBN 0-8176-4252-8
- Alison M. Marr y WD Wallis (2013), Magic Graphs . Segunda edicion. 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 gráficos. Revista electrónica de combinatoria , vol. 5, Encuesta dinámica 6. Actualizado muchas veces.