ピーターセングラフ

ピーターセングラフ

著者	デレク・ホルトン ジョン・シーハン
シリーズ	オーストラリア数学協会講演シリーズ
主題	ピーターセングラフ
出版社	ケンブリッジ大学出版局
発行日	1993

『ピーターセングラフ』は、ピーターセングラフとグラフ理論におけるその応用に関する数学書です。デレク・ホルトンとジョン・シーハンによって執筆され、1993年にケンブリッジ大学出版局からオーストラリア数学協会講演シリーズの第7巻として出版されました。

ピーターセングラフは、 10 個の頂点と 15 個の辺を持つ無向グラフで、通常は五角形の中に五芒星が描かれ、対応する頂点は互いに接続されています。このグラフには多くの珍しい数学的特性があり、グラフ理論の推測に対する反例として頻繁に使用されています。^{[1] [2]}この本では、これらの特性を利用して、このグラフが重要な役割を果たすグラフ理論の高度なトピックをいくつか取り上げています。^{[1] [3]}この本には豊富な図解があり、議論されているトピックに関する未解決の問題と、これらの問題に関する文献への詳細な参照が含まれています。^{[1] [4]}

導入章の後、第 2 章と第 3 章では、グラフ彩色、平面グラフの4 色定理の歴史、平面立方グラフの3 辺彩色との同値性、スナーク(そのような彩色を持たない立方グラフ)、すべてのスナークがピーターセン グラフをグラフマイナーとして持つというWT Tutteの予想について取り上げます。さらに 2 つの章では、完全マッチング(3 辺彩色で単一の色を持つことができる辺の集合) とnowhere-zero フロー(平面グラフ彩色の双対概念) という密接に関連するトピックについて取り上げます。ピーターセン グラフは Tutte の別の予想にも再び登場します。これは、ブリッジのないグラフがピーターセン グラフをマイナーとして持たない場合、nowhere-zero 4 フローを持つ必要があるというものです。 ^[3]

本書の第 6 章では、ケージ、つまり、与えられた長さより短いサイクルを持たない最小の正則グラフについて説明しています。ピーターセン グラフはその一例です。これは、長さが 5 より短いサイクルを持たない最小の3 正則グラフです。第 7 章は、すべての頂点を通るハミルトン サイクルを持たないが、1 つの頂点を除くすべての頂点の集合を通るサイクルを持つグラフである、ハイポハミルトン グラフについて説明しています。ピーターセン グラフは最小の例です。次の章では、グラフの対称性と、対称性によって定義されるグラフの種類について説明します。これには、距離推移グラフと強正則グラフ(ピーターセン グラフはその一例) ^[3]およびケイリー グラフ(ピーターセン グラフはそうではない) ^[1]が含まれます。本書は、各章に収めるには小さすぎるさまざまなトピックを扱った最終章で締めくくられています。^[3]

この本は、読者がすでにグラフ理論に多少精通していることを前提としています。^[3]この分野の研究者の参考書として、^{[1] [2]}またはグラフ理論の上級コースの基礎として使用できます。^{[2] [3]}

カーステン・トーマスセンはこの本を「エレガント」と評し、^[4]ロビン・ウィルソンは解説を「概ね良好」と評価しているが、 ^[2]評論家のチャールズ・HC・リトルは反対の見解を示し、校正や数学的表記法の一部、そして、あるグラフ分解の「ブリック」内のピーターセングラフのコピー数が次元の計算に重要な役割を果たす完全マッチングの整数組み合わせの格子について議論していない点を指摘している。^[1]評論家のイアン・アンダーソンは、一部の説明が表面的であると指摘しているが、この本は「グラフ理論の刺激的で熱狂的な一面を垣間見せることに成功している」と結論付けている。^[3]