>>> Complexity Seminar のお知らせ <<< 

発表：蓮沼  徹  hasunuma@kuamp.kyoto-u.ac.jp
　　　京都大学情報学研究科数理工学専攻

題目： de Bruijn 及び Kautz ダイグラフのページナンバー

日時：１９９９年１月２９日（金）３時３０分〜５時３０分

場所：電気通信大学　西９号館（おそらく３階）
      ＊部屋につきましては後ほどご連絡します．

内容：
ダイグラフのクラス S のページナンバーとは、S の任意の
ダイグラフが埋め込み可能な最小ページ数のことである。まず、
de Bruijn ダイグラフ B(d,D) 及び Kautz ダイグラフ K(d,D) が
(d+1)ページに埋め込み可能であることを証明する。この結果から、
d = 2 の場合には (d+1) が {B(d,D) | D \geq 1} 及び 
{K(d,D) | D \geq 1} のページナンバーであることが導かれる。
次に、d \geq 3 の場合には、ある定数 c が存在して、D > c ならば 
B(d,D) 及び K(d,D) は d ページに埋め込み不可能であることを証明する。
従って、任意の d \geq 2 に対して、{B(d,D) | D \geq 1} 及び 
{K(d,D) | D \geq 1} のページナンバーは (d+1)に決定される。

----

戸田誠之助