グラフの因子理論

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

グラフの因子問題は、与えられたグラフに対して、ある特定の性質をみたす全域部分グラフを見つけるという問題である。全域部分グラフとは、与えられたグラフのすべての点と一部の辺からなるグラフのことである。本年度は、主に次の2点に関する研究を行った。1.先の研究で導入した新たな因子の有用性、特にこの因子が存在するための簡明な十分条件に関する研究先の研究において既存の因子を多く含む新たな因子を定義し、グラフがその因子をもつための必要十分条件を得ることができた。しかし、これはかなり複雑な評価式であるため、グラフが所望の因子をもつための簡明な十分条件を求めた。本研究課題での主な結果の概略は、以下の通りである:グラフGにおいて、辺で結ばれていない2点の組すべてに対し、これらt点が隣接する点の個数がa|G|/(a+b)以上ならば、Gは[a,b]-因子をもつ。2.ハミルトン閉路を含む因子をもつための次数条件に関する研究ハミルトン閉路とは、グラフのすべての点を一度ずつ通る経路をいい、連結2-因子ともいえる。これは、工学的にも広く応用される概念のひとつであるが、因子理論的手法を取り入れた結果は、これまであまり知られていなかった。こうした中、本研究では、与えられたハミルトン閉路を含む[k,k+1]-因子をもつための次数条件を求めた。本研究課題での主な結果の概略は、以下の通りである:グラフGにおいて、互いに辺で結ばれていない2点の組すべてに対し、これら2点が隣接する点の個数が|G|/2以上ならば、Gは与えられたハミルトン閉路を含む[k,k+1]因子をもつ。