距離推移グラフ

距離推移グラフとは

距離推移グラフ（distance-transitive graph）とは、任意の距離だけ離れた二つの頂点の間に自己同型が存在する特性を持つグラフを指します。この概念はグラフ理論における重要な研究対象であり、特に頂点の距離や位置に対する対称性を強調しています。具体的に言うと、距離 i だけ離れた頂点 v と w がある時、同じ距離 i だけ離れた別の頂点 x と y に対して、v を x に、w を y に写すような自己同型が成り立ちます。

特徴と性質

距離推移グラフは、いくつかの重要な性質を有しています。まず、頂点推移的であること、つまりどの頂点もその他の頂点と同等に扱われるということが挙げられます。また、対称性を持ちつつ、各頂点が等しく接続される距離正則の性質も備えています。

また、距離推移グラフは一般に大きな自己同型群を持ち、これが数学的な興味を引きます。近年の研究において、直径が 2 の距離推移グラフは特に代表的なもので、いくつかの興味深い有限群の自己同型群がこの形式に該当します。

歴史的背景

この概念は、1971年にノルマン・L・ビッグスとD・H・スミスによって初めて明確に定義されました。彼らの研究では有限3価の距離推移グラフは12種類しか存在しないことを証明し、これにより距離推移グラフがどれだけ限定された構造かが示されました。

距離正則だが距離推移ではないグラフの存在

1969年、ロシアの数学者ゲオルギー・アデルソンヴェルスキーのチームは、距離正則でありながら距離推移グラフではないグラフも存在することを報告しました。特に、次数が 3 の場合においては、126 頂点のトゥッテ12-ケージというユニークな例が挙げられます。加えて、最小の距離推移的でない距離正則グラフはシュリクハンデグラフとして知られています。

しかし、次数が 3 よりも大きなグラフについては、完全な距離推移グラフのリストが確立されておらず、任意の頂点次数に対する距離推移グラフの分類は依然として未解決の課題となっています。

代表的な距離推移グラフ

距離推移グラフの中で最も基本的な例として挙げられるのが、超立方体グラフです。このグラフは、任意の次元における高次の 接続を示し、他にもfolded cube graphや正方ルークのグラフなどが存在します。これらのグラフはいずれも高次の次数を持つ特性があります。

まとめ

距離推移グラフは、その自己同型性や対称性により、数学界でも特に興味深い研究対象となっています。今後の研究によって、さらに多くの性質やタイプが解明されることが期待されます。距離推移グラフの研究は、数理的理解を深めるだけでなく、グラフ理論全体に新たな展開をもたらす可能性を秘めています。

もう一度検索