頂点推移グラフ

頂点推移グラフについての説明

定義

数学のグラフ理論において、頂点推移グラフ（ちょうてんすいいグラフ）とは、与えられた任意の二つの頂点、v1とv2に対して、ある自己同型関数fが存在し、f(v1) = v2を満たすグラフGのことを指します。この定義により、グラフの任意の頂点間での変換を可能にする性質を持っています。言い換えれば、グラフが頂点推移的である場合、その自己同型群がすべての頂点に対して可移的に作用することを意味します。

この特性を持つグラフは、その補グラフも頂点推移的であることが必要十分条件であることが知られています。これは、両者の群作用が等しいためです。

典型的な性質

頂点推移グラフの重要な性質には、孤立頂点を含まない対称グラフであることが挙げられます。全ての頂点が同じように扱われるため、正則性も求められます。しかし、頂点推移的であることは、自動的に対称性を意味するわけではありません。例えば、切頂四面体の辺から成るグラフは頂点推移的でも対称ではありません。また、同様に全ての正則グラフが頂点推移的であるわけでもなく、フルフトグラフがその一例です。

有限の頂点推移グラフの例

有限の頂点推移グラフの代表例としては、ピーターセングラフやヒーウッドグラフ、さらに正多面体の頂点及び辺から成るグラフが挙げられます。これらのグラフは全て有限であり、自己同型群の特性によって特徴付けられます。また、有限のケイリーグラフにおいても頂点推移的な性質が見られ、特にキューブ連結サイクルなどがその例として知られています。Potočnik、Spiga、Verretの研究によると、最大1280個の頂点を持つ全ての連結立体頂点推移グラフが調査されています。

性質の深掘り

頂点推移グラフの辺連結度はその次数dに等しいとされています。一方で、頂点連結度は少なくとも2(d + 1) / 3の範囲にあることが知られています。また、特定の条件下、例えばグラフの次数が4以下である場合、またはグラフが辺推移的である場合には、頂点連結度が次数dと等しくなることが示されています。

無限の場合

無限の頂点推移グラフには、無限路（両方向に無限に広がる）、無限正則木、平面一様充填のグラフ（正多角形によるタイル張りを含む）などが含まれます。無限ケイリーグラフやラドグラフもこれに該当します。最近の有名な予想には、全ての無限頂点推移グラフがケイリーグラフと準等距離同型であるとするものがありましたが、反例が示されたことで、この見方は変わりつつあります。

結論

頂点推移グラフは、グラフ理論において非常に興味深いトピックであり、その特性や関連する理論は学問的な探求を促します。グラフの自己同型性は、数学的な構造や性質を理解するための重要な手がかりを提供します。今後も、これらの概念がさらなる研究を通じて深化していくことが期待されています。

もう一度検索