| タイトル | グラフのタフネスとハミルトン閉路の存在性 |
|---|---|
| 開催日時 | 2021年6月22日 16時30分 |
| 主催者 | 内村朝樹、金村佳範、竹内裕隆 |
| 講演者 | 三家 雅弘 氏 |
| 場所 | |
| 内容 | グラフのハミルトン閉路とは、そのグラフの全ての頂点を通る閉路のことである。与えられたグラフがハミルトン閉路を持つかを判定する効率のよい方法は知られておらず、ハミルトン閉路はグラフ理論における研究対象のひとつとなっている。グラフのタフネスとは、そのグラフの頂点分離集合を用いて定義される不変量である。ハミルトン閉路を持つグラフは、タフネスが1以上であることが知られている。この命題の逆は成り立たないが、「ある定数tが存在して、タフネスがt以上となるグラフはハミルトン閉路を持つ」ことがChvatalにより予想されており、現在も未解決である。本発表では、Chvatalの予想に関連するいくつかの定理について、発表者が得た結果も含めて紹介する。 |
| 資料 | |
| URL | https://sites.google.com/keio.jp/mathscionlineseminar |
