グラフのラベル付け

グラフは、頂点が0からグラフのサイズである| E |までラベル付けされ、この頂点ラベル付けによって辺のラベル付けが1から| E |まで誘導される場合に、優美であると言われます。任意の辺eについて、 eのラベルは、eに接続する 2 つの頂点のラベルの正の差です。言い換えれば、e がラベルiとjの頂点に接続する場合、e のラベルは| i − j |になります。したがって、グラフG = ( V , E )は、 Vから{0, ..., | E | }への単射が存在し、それがEから{1, ..., | E | }への全単射を誘導する場合に限り、優美です。

ローザは自身の論文で、サイズが1または2 ( mod 4 )に相当するすべてのオイラーグラフは優美ではないことを証明した。特定のグラフ族が優美であるかどうかは、グラフ理論において広く研究されている分野である。おそらく、グラフラベル付けにおける最大の未証明の予想は、すべての木が優美であるという仮説であるリンゲル・コッツィヒ予想である。これは、すべてのパス、キャタピラー、およびその他多くの無限の木族について証明されている。アントン・コッツィヒ自身は、この予想を証明しようとする努力を「病気」と呼んでいる。^{[ 6 ]}

ループや多重辺のない単純グラフにおいて、p個の頂点とq個の辺に対して、辺を{1, …, q }の異なる整数でラベル付けする。このラベル付けによって、頂点に隣接する辺の合計をpで割った余りをラベル付けすると、頂点には0からp -1までのすべての値が割り当てられる。グラフGは、このような辺のラベル付けが可能な場合、「辺優美」であると言われる。

エッジグレースフルラベル付けは、1985年にSheng-Ping Loによって初めて導入されました。^{[ 7 ]}

グラフがエッジグレースであるための必要条件は「ローの条件」である。

${\displaystyle q(q+1)={\frac {p(p-1)}{2}}\mod p.}$

グラフGの「調和ラベル付け」とは、 Gの頂点から、kを法とする整数群への単射であり、辺( x , y )の辺ラベルを 2 つの頂点 x, y (mod k) のラベルの合計とすることで、Gの辺と法 kの数の間に全単射を誘導するものです。「調和グラフ」とは、調和ラベル付けを持つグラフのことです。奇数サイクルは調和的であり、ピーターセングラフも同様です。1つの頂点ラベルの再利用が許されるならば、木はすべて調和的であると推測されています。^{[ 8 ]} 7 ページのブックグラフK1,7 × K2_は、調和的ではないグラフの例を示しています。^{[ 9 ]}

グラフ彩色とは、グラフラベル付けのサブクラスである。頂点彩色では隣接する頂点に異なるラベルを割り当て、辺彩色では隣接する辺に異なるラベルを割り当てる。^{[ 10 ]}

グラフGのラッキー ラベリングとは、 Gの頂点に正の整数を割り当てることで、S ( v ) がvの隣接頂点のラベルの合計を表す場合、SはGの頂点彩色となるようなものである。Gの「ラッキー ナンバー」とは、G が整数{1, …, k } でラッキー ラベリングを持つ最小のkである。^{[ 11 ]}

グラフGの反魔法ラベル付けとは、 Gのエッジに正の整数{1,..., | E | } を 1 対 1 で割り当て、誘導されるすべての頂点の重みが互いに異なるようにすることであり、頂点の重みは、その頂点に接続するすべてのエッジのラベルの合計である。^{[ 12 ]}

グラフGの（距離）マジック ラベリングとは、 Gの頂点に正の整数{1,..., | V | } を 1 対 1 で割り当て、すべての頂点の重みが正の整数kに等しくなるようにすることです。頂点の重みは、その頂点に隣接するすべての頂点のラベルの合計です。このような定数kが存在する場合、それはグラフのマジック定数と呼ばれます。