グラフの点素な閉路に関する極値問題

今年度は1.2部グラフにおける指定した頂点数3のパスを含む閉路による分割2.指定した線形林を含む閉路によるグラフの分割3.いくつかの頂点の次数が制限された全域木の存在について取り組んだ。これまでの研究では、指定された頂点や辺を含む閉路によるグラフの分割を考えてきたが、その一般化として、線形林を指定して、それらを含む閉路による分割が考えられる。一般的には頂点と辺を指定した場合の結果を用いることにより、容易に最良の次数条件が求められるが、それには当てはまらないケースもいくつかある。2.の研究ではそのような状況を特定し、その場合における最良の次数条件を求めた。2部グラフにおいては線形林を考える際の元となる頂点と辺を含んだ場合の問題も未解決である。線形林の部分的な問題として、頂点数が3のパスを指定した場合を1.で考え、こちらも最良の次数条件が求まった。2部グラフにおいては頂点数が奇数のパスは辺の場合と大きく状況が異なるため、一般的な問題の解決への1歩になったのではないかと考えている。3.は昨年度より取り組んでいる全域木の研究である。今年度は(1)指定された頂点を含み、全体の次数が制限された部分木(2)指定された頂点については次数が制限された全域木、が存在するための次数条件を考え、最良の条件を求めることが出来た。この研究はこれまで閉路に関する研究で考えられてきた考え方を木の問題に適用したものであり、これまであまりなされていなかったものである。この結果については7月にイギリスで行なわれた「British Combinatorial Conference」および9月にフランスで行なわれた「International Colloquium on Graph Theory」において研究発表を行なった。

今年度は1.2部グラフにおける指定した頂点数3のパスを含む閉路による分割2.指定した線形林を含む閉路によるグラフの分割3.いくつかの頂点の次数が制限された全域木の存在について取り組んだ。これまでの研究では、指定された頂点や辺を含む閉路によるグラフの分割を考えてきたが、その一般化として、線形林を指定して、それらを含む閉路による分割が考えられる。一般的には頂点と辺を指定した場合の結果を用いることにより、容易に最良の次数条件が求められるが、それには当てはまらないケースもいくつかある。2.の研究ではそのような状況を特定し、その場合における最良の次数条件を求めた。2部グラフにおいては線形林を考える際の元となる頂点と辺を含んだ場合の問題も未解決である。線形林の部分的な問題として、頂点数が3のパスを指定した場合を1.で考え、こちらも最良の次数条件が求まった。2部グラフにおいては頂点数が奇数のパスは辺の場合と大きく状況が異なるため、一般的な問題の解決への1歩になったのではないかと考えている。3.は昨年度より取り組んでいる全域木の研究である。今年度は(1)指定された頂点を含み、全体の次数が制限された部分木(2)指定された頂点については次数が制限された全域木、が存在するための次数条件を考え、最良の条件を求めることが出来た。この研究はこれまで閉路に関する研究で考えられてきた考え方を木の問題に適用したものであり、これまであまりなされていなかったものである。この結果については7月にイギリスで行なわれた「British Combinatorial Conference」および9月にフランスで行なわれた「International Colloquium on Graph Theory」において研究発表を行なった。