曲面上のグラフの組合せ論的性質に関する研究

閉曲面を1つ固定したとき、そこに埋め込まれたグラフの辺の密度は、オイラーの公式により制限を受ける。さらに、辺の密度の高いグラフに縮約できないことから、グラフのtoughnessがある程度高いことがわかる。一般に、グラフのtoughnessはハミルトン閉路の存在と深い関わりがあることが指摘されている。曲面上のグラフについて言えば、とくに、4連結平面グラフは1-toughであり、ハミルトン閉路をもつことが知られている。本研究では、この事実の3連結平面グラフへのアナロジーを考え、すべての点の次数が2または3であるような連結全域部分ブラフの存在に関する結果を得た。曲面に埋め込まれたグラフの研究においては、通常、曲面の位相同型による差は無視して考える。ところが、同じ曲面に埋め込まれた2つのグラフの関係を考える場合には、そのねじれ具合までを考慮しなければならないことがある。一般に、種類1以上の閉曲面においては、同一のグラフの、組合せ的には全く同じ埋め込みでも、連続変形では移り合えないものが無数に存在する。閉曲面の三角形分割やある種の四角形分割については、従来の研究で、2つのグラフの頂点数が十分多く等しければ、対角変形と呼ばれる局所的な変形の繰り返しで、組合せ的意味で互いに移り合えることが知られていた。この事実を一歩押し進め、連続変形では移り合えないもの同士も、対角変形をさらに繰り返すことで移り合えることを示した。これにはDehn twistと呼ばれる閉曲面の位相同型がこの対角変形によって実現できることを用いたが、これは、曲面上に埋め込まれたグラフを、ねじれまで考慮していかに組合せ的に議論するかのひとつの方法を与えるものとなったと思われる。

閉曲面を1つ固定したとき、そこに埋め込まれたグラフの辺の密度は、オイラーの公式により制限を受ける。さらに、辺の密度の高いグラフに縮約できないことから、グラフのtoughnessがある程度高いことがわかる。一般に、グラフのtoughnessはハミルトン閉路の存在と深い関わりがあることが指摘されている。曲面上のグラフについて言えば、とくに、4連結平面グラフは1-toughであり、ハミルトン閉路をもつことが知られている。本研究では、この事実の3連結平面グラフへのアナロジーを考え、すべての点の次数が2または3であるような連結全域部分ブラフの存在に関する結果を得た。曲面に埋め込まれたグラフの研究においては、通常、曲面の位相同型による差は無視して考える。ところが、同じ曲面に埋め込まれた2つのグラフの関係を考える場合には、そのねじれ具合までを考慮しなければならないことがある。一般に、種類1以上の閉曲面においては、同一のグラフの、組合せ的には全く同じ埋め込みでも、連続変形では移り合えないものが無数に存在する。閉曲面の三角形分割やある種の四角形分割については、従来の研究で、2つのグラフの頂点数が十分多く等しければ、対角変形と呼ばれる局所的な変形の繰り返しで、組合せ的意味で互いに移り合えることが知られていた。この事実を一歩押し進め、連続変形では移り合えないもの同士も、対角変形をさらに繰り返すことで移り合えることを示した。これにはDehn twistと呼ばれる閉曲面の位相同型がこの対角変形によって実現できることを用いたが、これは、曲面上に埋め込まれたグラフを、ねじれまで考慮していかに組合せ的に議論するかのひとつの方法を与えるものとなったと思われる。