半対称グラフ

半対称グラフとは

半対称グラフは、数学のグラフ理論における特異な構造を持つ無向グラフであり、辺推移的かつ正則ですが、頂点推移的ではありません。これはつまり、各頂点が等しい数の辺を持っているという対称性を示しますが、特定の頂点のペアに対してその対称性が完全に適用されないことを意味しています。特に、ある頂点が別の頂点に写ることができない場合も存在します。

性質と構造

半対称グラフは二部グラフとしての特性を示します。その自己同型群は、二部の各頂点の集合に対して推移的に作用します。例えば、ある頂点が他の頂点に写される際、特定の頂点を緑、他の頂点を赤とした場合、緑の頂点はどのような自己同型の操作においても赤の頂点に変換されることがなく、このような性質が半対称の根幹を成しています。

歴史的背景

半対称グラフの概念は1967年に、ジョン・フォークマンによって引き立てられました。彼は20頂点を持つ最小の半対称グラフ、通称フォークマングラフの発見により、この分野の研究を促しました。その後、最小の立方体半対称グラフとして54頂点のグレイグラフがBouwerによって1968年に確認されました。また、ドラガン・マルシッチとアレクサンダー・マルニッチはそれが立方体半対称グラフであることを証明しました。

立方体半対称グラフの探索

現在、立方体半対称グラフは768頂点のものまで広がりがあり、研究が進められています。特に、グレイグラフに続く最小の四つの立方体半対称グラフには、以下のものが確認されています：

• - 110頂点のイオフィノヴァ-イヴァノフグラフ
• - 112頂点のリュブリャナグラフ
• - 120頂点の内周8のグラフ
• - トゥッテ-12ケージ

これらの構造は、数学的な興味を引きつけており、さらなる研究の基礎となっています。

まとめ

半対称グラフは、単なるグラフではなく、独特の対称性と構造を持つことで、数学において更なる探求の道を提供しています。その特異な性質は、グラフ理論の進展に寄与しており、今後も新たな発見を促す要素として機能することでしょう。興味がある方はぜひ、半対称グラフの研究を進めてみてください。

もう一度検索