エッジグレースフルなラベル付け

Edge-graceful_labeling
グラフ理論では、エッジグレースフルラベル付けは、2 つの異なるエッジが同じ 2 つの異なる頂点を接続せず、頂点をそれ自体に接続するエッジがない単純な接続グラフのグラフラベル付けの一種です。
エッジグレースフルなラベリングは、Sheng-Ping Lo によって彼の独創的な論文で最初に紹介されました。

コンテンツ
1 意味
2 例
2.1 サイクル 2.2 パス
3 必要条件
4 さらに選択された結果
5 参考文献

意味
グラフGが与えられたとき、辺の集合をE ( G )で、頂点をV ( G )で表します。qをE ( G )のカーディナリティとし、pをV ( G )のカーディナリティとします。エッジのラベリングが与えられると、グラフの頂点uは、それに付随するエッジのラベルの合計、モジュロpによってラベル付けされます。または、シンボルでは、頂点uの誘導ラベル付けは次のように与えられます。 Ⅴ ( あなた) = Σ え( e ) モッド
| | Ⅴ ( G ) | |
{ V(u)=Sigma E(e)mod |V(G)|}
$V(u)=Sigma$
ここで、V ( u )は頂点のラベルで、E ( e )はuに付随するエッジに割り当てられた値です。
問題は、1 からqまでのすべてのラベルが 1回使用され、頂点上の誘導されたラベルが 0 からp – 1まで続くように、エッジのラベル付けを見つけることです。つまり、エッジのラベルの結果セットは、{1， 2， …， q }および頂点の{0， 1， …， p – 1}になります。
グラフGは、エッジグレースフルなラベル付けを許容する場合、エッジグレースフルであると言われます。

例

サイクル

C 5の端正なラベリング
3 つの頂点C 3を持つサイクルを考えてみましょう。これは単なる三角形です。エッジ 1、2、および 3 にラベルを付けて、頂点で誘導されたラベル付けとともに、これがエッジグレースフルなラベル付けを与えることを直接確認できます。パスと同様に、C mは、 mが偶数の場合ではなく、 mが奇数の場合にエッジグレースフルです。

パス
2 つの頂点P 2を持つパスを考えます。ここで唯一の可能性は、グラフ 1 の唯一のエッジにラベルを付けることです。2 つの頂点に誘導されたラベルは両方とも 1 です。したがって、P 2はエッジグレースフルではありません。
エッジと頂点をP 2に追加すると、 3 つの頂点を持つパスであるP 3が得られます。頂点をv 1、v 2、およびv 3で表します。次の方法で 2 つのエッジにラベルを付けます: エッジ( v 1 ， v 2 )は 1 とラベル付けされ、 ( v 2 ， v 3 )は 2 とラベル付けされます。v 1、v 2、およびv 3で誘導されたラベル付けは、1、0 です。、および 2 です。これはエッジグレースフルなラベル付けであるため、P 3はエッジグレースフルです。
同様に、 P 4がエッジグレースフルではないことを確認できます。
一般に、P mは、 mが奇数の場合はエッジグレースフルであり、偶数の場合はエッジグレースフルではありません。これは、エッジグレースフルネスの必要条件から導かれます。

必要条件
Lo は、 q 個のエッジとp個の頂点を持つグラフがエッジグレースフルであるために必要な条件を与えました。 q ( q + 1)は、p ( p – 1)/2mod p . 記号で: q ( q+ 1 ) ≡ p( p− 1 ) 2
モッドp .
{ q(q+1)equiv {frac {p(p-1)}{2}}mod p.}

これは、文献ではローの状態と呼ばれています。これは、頂点のラベルの合計がエッジの合計の 2 倍であるという事実から導かれます (モジュロp )。これは、グラフがエッジグレースフルであることを反証するのに役立ちます。たとえば、これを上記のパスとサイクルの例に直接適用できます。

さらに選択された結果
Petersen グラフはエッジグレースフルではありません。
スターグラフ S メートル
{ S_{m}}
(中央ノードと長さ 1 のm脚) は、 mが偶数の場合はエッジグレースフルであり、 mが奇数の場合はエッジグレースフルではありません。
友情グラフふメートル
{ F_{m}}

mが偶数の場合ではなく、奇数の場合はエッジグレースフルです。
通常の木， T メートル n
{ T_{m，n}}
(各非リーフノードがm個の新しい頂点を放出する深さn ) は、 mが任意の値n に対して偶数の場合はエッジグレースフルですが、 mが奇数の場合は常にエッジグレースフルではありません。
n頂点上の完全なグラフ、
K n { K_{n}}

、 nが単独で偶数でない限り、エッジグレースフルです。n = 2
モッド 4 { n=2mod 4}
. ラダーグラフは決してエッジグレースフルではありません。

参考文献
^ Lo， Sheng-Ping (1985). 「グラフのEdge-Graceful Labelingsについて」。コングレスヌメランティウム。ユタ州サンダンス会議。巻。50. pp. 231–241. Zbl 0597.05054 .
^ Q. Kuan、S. Lee、J. Mitchem、および A. Wang (1988)。「エッジグレースフル単環式グラフについて」。コングレスヌメランティウム。61 : 65–74.
^ L. リー、S. リー、および G. マーティ (1988)。「完全なグラフのエッジグレースフルラベル付けについて: Lo の予想の解決策」. コングレスヌメランティウム。62 : 225–233.
^ D. スモール (1990)。「通常の (偶数の) スパイダーグラフはエッジグレースフルです」. コングレスヌメランティウム。74 : 247–254.
^ S. カバニス、R. ロー、J. ミッケム (1992)。「On Edge-Graceful Regular Graphs and Trees」. アルス・コンビナトリア。34 : 129–142.
“

エッジ グレースフルなラベル付け