木の(<i>p</i>, <i>q</i>)-全ラベリング問題

概要

論文の詳細を見る
グラフ G の k-(p,q)-全ラベリングとは,G の節点と辺への 0 から k までの整数値の割当てであり,節点とそれに接続する辺の間では少なくとも p,隣接する 2 節点間または 2 辺間では少なくとも q の差があるもののことをいう.G の (p, q)-全ラベリング数 λTp;q(G) は,k がとりうる値の最小値として定義される.G の (p, q)-全ラベリング問題とは,ラベリング数 λTp;q(G) を求める問題である.本研究では,いくつかのグラフクラスのグラフの (p, q)-全ラベリング数に対して新しい上界と下界を与える.とくに,グラフが木の場合にはタイトな上界と下界を与える.また,グラフが木で p≦3q/2 の場合に (p, q)-全ラベリング問題を解く線形時間アルゴリズムを与え,さらに最大次数が 4 以上という仮定が加わった場合,λTp;q(T) を実現する木Tを完全に特徴づけられることも示す.この結果は,(p; q)-全ラベリング問題の一般化である L (p; q)-ラベリング問題が q が p の約数でないすべての (p; q) の組に対し NP 困難であることと対照的である.
2010-11-12