魔法のグラフ

マジックグラフとは、辺が最初のq個の正の整数でラベル付けされているグラフ(qは辺の数)であり、どの頂点に接する辺の合計も、頂点の選択とは無関係に同じになるグラフ、またはそのようなラベル付けを持つグラフです。「マジック」という名前は、整数が任意の正の整数であることを意味する場合もあります。その場合、最初のq個の正の整数を使用したグラフとラベル付けは、スーパーマジックと呼ばれます。

グラフの頂点にラベルを付けることが可能で、どの辺の合計も同じである場合、そのグラフは頂点マジックです。グラフの辺と頂点にラベルを付けることが可能で、頂点ラベルとその頂点に接する辺のラベルの合計が一定である場合、そのグラフ は完全マジックです。

グラフのマジックラベル付けの概念には、非常に多くのバリエーションがあります。用語にも多くのバリエーションがあります。ここでの定義は、おそらく最も一般的なものです。

魔法のラベル付けと魔法のグラフに関する包括的な参考文献としては、Gallian (1998)、Wallis (2001)、Marr and Wallis (2013) があります。

セミマジックスクエアは、セルに 1 からn ²までの数字が入り、各行と各列の合計が同じになるn  ×  n の正方形です。セミマジックスクエアは、完全な二部グラフK _n、nのマジックラベル付けに相当します。 K _n、nの 2 つの頂点セットは、それぞれ正方形の行と列に対応し、辺r _i s _jのラベルは、セミマジックスクエアの行i、列jの値です。  

半魔方陣の定義は、方陣の対角線の扱いにおいて魔方陣の定義と異なります。魔方陣は、対角線の合計が行と列の合計と同じである必要がありますが、半魔方陣ではこれは必要ありません。したがって、すべての魔方陣は半魔方陣ですが、その逆は当てはまりません。

• Nora Hartsfield およびGerhard Ringel (1994、2003)、「Pearls in Graph Theory」、改訂版。Dover Publications、ニューヨーク州ミネオラ、セクション 6.1。
• WD Wallis (2001)、「Magic Graphs」、Birkhäuser Boston、マサチューセッツ州ボストン、 ISBN  0-8176-4252-8
• Alison M. Marrおよび WD Wallis (2013)、「Magic Graphs」。第 2 版。Birkhäuser/Springer、ニューヨーク。ISBN 978-0-8176-8390-0 ; 978-0-8176-8391-7 
• Joseph A. Gallian (1998)、「グラフラベル付けの動的調査」。Electronic Journal of Combinatorics、vol. 5、Dynamic Survey 6。何度も更新されています。