グラフにおける長い閉路の存在性について

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

平成18年度は次の予想を掲げ、以下の証明方法で予想の解決に努めた。[予想]グラフGがk連結グラフ(k≧3)ならば、Gにはk個の頂点からなる頂点集合Wを通る長さmin{|V(G)|,2μ(G)-1}以上の閉路が存在する。ここで、μ(G)=min{max{d(u),d(v)}:d(u,v)=2}とする。(証明方法)指定した頂点集合Wの頂点数kに関する帰納法による証明を考える。このとき帰納法の仮定より、グラフGには指定した頂点集合のk-1個の頂点を通る長さmin{|V(G)|,2μ(G)-1}以上の閉路が存在する。(今、この状況下において最長閉路Cを考える。)W⊆V(C)ならば予想は成り立つので、W〓V(C)、すなわちW-V(C)={w}としてよい。以下、wを含むG-V(C)の連結成分Hが2連結グラフである場合と、そうでない場合に分け証明を行う。上記証明方法では、連結成分Hが2連結グラフでない場合の証明が重要となる。このとき、Hは1個以上のブロックから構成されているが、頂点wがどのブロックに含まれているかによって、証明が非常に複雑なものとなる。また、最長閉路Cの長さを求める際に、すでに最長閉路C上にある頂点集合Wの位置に注意し、Cの長さを計算しなければならない。これまで、上記証明方法に従って様々な方法を試みてきたが、現在、予想の解決には至っていない。今後は上記予想のもとになっている定理を証明する際に用いた手法、すなわち、Vineと呼ばれる特殊な通路を用いた手法に改良を加えるなどして、予想の解決に努めていきたいと考えている。