The L(2,1)-labeling on the skew and converse skew products of graphs

Zhendong Shao, Roger K. Yeh and David Zhang
Applied Mathematics Letters
Volume 20, Issue 1 , January 2007, Pages 59-64
http://dx.doi.org/10.1016/j.aml.2006.02.032

無向グラフのL(2,1)-ラベリングとは，頂点への非負整数 (ラベル) の割当で，距離が1の頂点同士のラベルの差の絶対値は2以上，距離が2の頂点同士のラベルの差の絶対値は1以上という条件を満たすもの．
GのL(2,1)-ラベリングの中で使用する最大整数を見て，それが最小になるようなラベリングにおけるその値をGのL(2,1)-ラベリング数という．
Griggs & Yehはこの数が最大次数の2乗以下になる (ただし，最大次数は2以上の場合に限る) ことを予想したが，今のところ最善の上界は最大次数の2乗＋最大次数−1 (Kral & Skrekovski)．
この論文では，Shibata & Kikuchiの提案したグラフのskew productとconverse skew productに対して，元のグラフの最大次数が2以上ならば予想が成り立つことを示している．
L(2,1)-ラベリングはチャネル割当問題の単純化バージョンとしてよく出てくる問題の1つで，最近研究が進んでる．