名前	小関　健太
	所属	基礎理工学専攻/数理科学専修
	研究分野	離散数学,グラフ理論

グラフの不変量とハミルトン閉路に代表される各種閉路の存在との関係について
私の専門分野は離散数学，特にグラフ理論です．グラフとは、頂点集合と、辺集合（頂点集合の二元部分集合族）からなる構造として定義されます．このグラフ上での様々な性質・構造に関して調べる分野がグラフ理論であります．
グラフ理論の研究の一方向として，特定の部分構造の存在に関する研究が挙げられます．例えば，グラフの全ての頂点を丁度一度ずつ通る閉路をハミルトン閉路と呼びますが，「グラフがハミルトン閉路をもつかどうか決定する」という問題は，組み合わせ最適化の分野において特に重要な巡回セールスマン問題と密接に関係しているため，グラフ理論の中でも非常に多くの研究がなされています．このような「ハミルトン閉路に代表されるような特定の部分構造の存在を保証する条件」に関する研究が重要とされており，これが私の主な研究内容であります．
グラフの辺数が多ければ，ハミルトン閉路等の部分構造を見つけやすい，ということは直感的にわかります．例えば，n 頂点グラフにおいて辺数が (n² -3n +6)/2 本以上存在すれば，そのグラフはハミルトン閉路をもつことが簡単に示せます．また，それより辺数の少ないグラフでハミルトン閉路を持たないものが存在することも知られています．しかしながら，この辺数はグラフの構造を全く考慮しないものであり，そのため約 n²/2 本という非常に多くの辺が必要となります．
その一方で 1952年に Dirac が「 n 頂点グラフの最小次数（頂点に接続する辺数の最小値）が n/2 以上であれば，そのグラフはハミルトン閉路を持つ」という定理を示しています．この条件を Dirac 条件と呼びますが，Dirac 条件を満たすグラフの中で辺数が最小なものは n²/4 本の辺から構成されます．これは辺数条件のときの約半分の値です．したがって最小次数という，辺数よりもある意味``本質的''なグラフの不変量を考慮することにより，グラフのハミルトン閉路の存在性に関してより詳しく調べることが可能になることがわかります．
このようにハミルトン閉路を中心としたグラフの部分構造に関して，より本質的な不変量条件を模索することが私の一番の興味の対象です．具体的には上記の次数に加え，連結度，独立数，などの不変量と，閉路，パス，全域木などのグラフの部分構造との関係について研究を行っています．