多次元トーラスグラフの線形配置

概要

論文の詳細を見る
グラフGの線形配置Lとは, Gの点集合V(G)から整数の集合{1, 2, …, |V(G)|}の上への一対一の写像である.Lの各値は.数直線上の位置とみなせるので, グラフの全ての辺vwについての値|L(v)-L(w)|の総和をLの総辺長と呼ぶ.2つの正整数nとmの組に対して, n-次元m-トーラスグラフと呼ばれる無向グラフT^n_mを次のように定義する.T^n_mの点集合は, すべての〓_m-値n-次元ベクトルからなる集合であり, 辺集合は, 差のノルムが丁度1である2つの点を結ぶ辺すべてからなる集合である.T^n_mの自然は配置とは, 各点を非負整数のm進表現とみなして昇順に並べる線形配置のことである.ただし, 第n成分を最上位桁とみなし, 〓_mの要素を0からm-1までの整数とみなす.本報告では, すべての正整数nに対して自然配置の総辺長がT^n_3のすべての線形配置の総辺長中最小であることを証明する.更に, T^n_3の線形配置のうち総辺長が最大であるものの完全な特長付けを与える.
社団法人電子情報通信学会の論文
2001-09-07