再帰的条件による成分因子の存在性に関する研究

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

グラフ理論における再帰的条件におけるある種の構造の存在性定理は、これまでに次の2つのTypeのものが最も基本的なものとして研究されてきている。Gを連結グラフ、HをGの任意の連結誘導部分グラフで位数を固定したものとする。さらにPをグラフのもつ性質とするとき、TypeI:Hが性質Pをもつ⇒Gも性質PをもつTypeII:G＼Hが性質Pをもつ⇒Gも性質PをもつKを連結グラフとし、Pが「K-成分因子をもつ」ということに対して、1986年にEnomoto, Egawa, SaitoによってTypeIが成立することが示されている。ここでの研究実績としては、「K-成分因子をもつ」ということに対するTypeIIの定理が完成させることができた。この結果は、JOurnal of Graph Theory誌において掲載受理を受けた。さらに、新しいTypeの再帰的条件としてTypeIII:H及びG＼Hがともに連結となる任意のHに対し、H(又はG＼H)が性質Pをもつ⇒Gも性質Pをもつということに対し、「K-成分因子をもつ」という結果については解決をみていないが、Gが2連結で、Pが「P_<3->因子をもつ」ということに対しては、TypeIIIが成立することが、この研究において証明することができた。グラフが成分因子をもつための必要十分条件を得ることはNP-完全問題であり、十分条件を得る研究ですらあまり進んでいない状態であったが、この研究において、2つの十分条件を得るに至ることができた。