対称グラフ

対称グラフの概要

数学のグラフ理論における対称グラフとは、特定の自己同型群の性質によって定義されるグラフです。対称グラフにおいては、任意の隣接する頂点のペアに対して、自己同型が存在し、その結果として頂点ペアが相互に変換可能であることを意味します。この自己同型は、グラフの構造を保ちながら頂点を入れ替える力をもち、具体的には、任意の隣接頂点ペア u1—v1 と u2—v2 に対して、f(u1) = u2 および f(v1) = v2 となる関係が成立する必要があります。

対称グラフの特性

一般に、対称グラフは1-弧推移的または旗推移的とも称され、その性質から、孤立頂点を持たない場合には必ず頂点推移的であることが分かります。また、対称グラフはその辺に対しても推移的であるため、辺の同型変換にも適用されます。しかし、辺推移的なグラフが必ずしも対称であるとは限らず、いくつかのグラフがこの条件に該当する例外も存在します。

例えば、半対称グラフは辺推移的かつ正則でありますが、同時に頂点推移的ではないため、より特異な性質を持つことになります。全ての連結対称グラフは頂点推移的であり、また辺推移的でもある一方で、偶数次数のグラフにおいては対称でない連結グラフも存在し得ます。これらは半推移的と呼ばれ、例えば、次数4のホルトグラフがその最小の例となります。

t-推移グラフとその定義

t-推移グラフの概念についても触れておきます。t-弧は、連続する任意の二つの頂点が隣接し、かつ繰り返し現れる頂点は二段階以上離れている列として定義されます。t-推移グラフは、その自己同型群がt-弧に対して推移的に作用するが、(t+1)-弧には作用しないグラフを指します。これにより、1-弧は単純に辺を表すため、対称グラフはtの値に伴う条件を満たすことになります。

対称グラフの実例

対称性を持つグラフの具体例として、立方体型のグラフがあります。これらのグラフは非常に特異な特性を有し、リスト化することも可能です。特に、1930年代のフォスター調査では、これらのグラフの包括的なリストが作成され、1988年にはその最新の調査報告が行われました。この報告書には、512個の頂点を持つ全ての立方体対称グラフが含まれています。

その中での具体的な例としては、ディックグラフ、フォスターグラフ、ビッグス-スミスグラフなどが挙げられます。これらは、各々が特に認識されている立方体型の対称グラフであり、いくつかは距離推移的な性質も有しています。また、他にも閉路グラフや完全グラフ、正八面体、正二十面体といったグラフも対称性を持つことが知られています。無限の次数を持つグラフの例としては、ラドグラフも挙げられます。

性質と結論

対称グラフに共通する特性として、頂点連結度は常にその次数dに等しく、逆に頂点推移グラフは一般的にこの値よりも下回ることがあります。また、t-推移グラフにおいては、内周が少なくとも2(t–1)となることがわかっていますが、特にtが8以上の場合には、有限のt-推移グラフは存在しないことが確認されています。これらの性質を考慮すると、対称グラフはその調査および分類において非常に重要な概念であると言えます。

もう一度検索