ツチヤ　ショウイチ   TSUCHIYA Shoichi   土屋 翔一    所属   専修大学  ネットワーク情報学部    職種   教授
言語種別	日本語
発行・発表の年月	2013/10
形態種別	研究論文（学術雑誌）
査読	査読あり
標題	Forbidden Subgraphs and the existence of a spanning tree without small degree stems
執筆形態	共著
掲載誌名	Elsevier ・Discrete Mathematics
巻・号・頁	(313),2206-2212頁
著者・共著者	古谷倫貴
概要	グラフGにおいて、次数2の頂点をもたないspanning treeをGのHomeomorphically irreducible spanning tree(HIST)とよぶ。HISTの存在判定問題は高さの低いspanning tree を探す問題と関連があり、情報科学への応用が期待される。グラフ理論では、特定の性質について禁止部分グラフを用いた特徴づけについて多くの研究がある。本論文では、ラムゼー数を用いて、頂点数が十分に大きい連結グラフにおいてHISTの存在を保証するための禁止部分グラフの族を完全決定する。また、HISTの一般化である[2、K]-spanning tree(次数2~kの頂点を持たない全域木)についても、同様の命題が成り立つ子を示す。本論文はHISTと禁止部分グラフの関連を扱った世界初の論文である。また、与えられたグラフがHISTを持つかを決定することはNP完全であることが示されているが、本論文では必要十分条件の形で定理を得た。そのため、本論文は新規性と定理の重要性が評価され、離散数学における一流学術誌であるDiscrete Mathematicsに受理・掲載された。