離散システムに付随するグラフ構造とその生物学への応用についての研究

点击翻译按钮获取中文摘要

今年度は、主にグラフの競争数に関する問題に取り組んだ。今年度の研究成果は、以下の通りである。(1)グラフにおいてその中のホールの指標ベクトルのなす線形空間をホール空間と呼ぶ。これは、グラフのサイクル空間の部分空間である。ホール空間の次元と競争数の関係について研究を行った。その結果、いくつかのグラフ・クラスに対し、競争数はホール空間の次元+1以下となっていることを示した。(2)各頂点部集合のサイズがnの完全m部グラフK^m_nの競争数について研究を行った。その結果、mが2以上の時K^m_2の競争数はmの値にかかわらずちょうど2、mが3以上の時K^m_3の競争数はmの値にかかわらずちょうど4であることが明らかになった。(3)1970年にHoffmanによって導入された概念である一般化ライングラフについて、その競争数の研究を行った。一般化ライングラフは、ライングラフとカクテルパーティーグラフの共通の一般化である。それぞれ、その競争数は2以下であることが知られているが、一般化ライングラフについても常に2以下となることが明らかになった。(4)グラフに対し、そのライングラフとmステップグラフが同型になるのはどういう場合かというグラフ方程式に関する研究を行った。そして、そのようになるための必要十分条件を与え、そのようなグラフの完全な分類による特徴づけを与えた。