対称グラフ

ピーターセングラフは（立方）対称グラフです。任意の5頂点環は任意の5頂点環に写像できるため、任意の隣接する頂点のペアは自己同型によって別の頂点に写像できます

数学のグラフ理論の分野において、グラフGが対称的または弧推移的であるとは、 Gの任意の2つの隣接する頂点 の順序付きペアとに対して、自己同型が存在する場合を言う。${\displaystyle (u_{1},v_{1})}$ ${\displaystyle (u_{2},v_{2})}$

${\displaystyle f:V(G)\rightarrow V(G)}$

となる

${\displaystyle f(u_{1})=u_{2}}$ そして^{[ 1 ]}${\displaystyle f(v_{1})=v_{2}.}$

言い換えれば、グラフが対称的であるとは、その自己同型群が隣接する頂点の順序付き対（つまり、方向を持つとみなされる辺）に推移的に作用する場合です。 ^{[ 2 ]}このようなグラフは、1弧推移的^{[ 2 ]}またはフラグ推移的[ ^{3 ]とも呼ばれます}

定義により（u ₁とu ₂を無視）、孤立した頂点のない対称グラフは、頂点推移的でなければなりません。^{[ 1 ]}上記の定義では、1つの辺を別の辺にマッピングするため、対称グラフは辺推移的でなければなりません。ただし、a—bはc—dにマッピングされる可能性がありますが、d—cにはマッピングされないため、辺推移グラフは対称である必要はありません。スターグラフは、頂点推移でも対称でもないが辺推移的である単純な例です。さらに例として、半対称グラフは辺推移的で正則ですが、頂点推移的ではありません。

自己同型によって定義されるグラフ族
距離推移	→	距離正則	←	強く正則
↓
対称（弧推移的）	←	t推移的、t  ≥ 2		歪対称
↓
（連結されている場合）頂点推移的および辺推移的	→	辺推移的かつ正則的	→	辺推移的
↓		↓		↓
頂点推移的	→	正則	→	（二部の場合）双正則
↑
ケーリーグラフ	←	ゼロ対称		非対称

したがって、連結された対称グラフはすべて、頂点推移的かつ辺推移的である必要があり、逆は奇数次グラフに対しても成り立ちます。^{[ 3 ]} しかし、偶数次では、頂点推移的かつ辺推移的だが対称ではない連結グラフが存在します。^{[ 4 ]}このようなグラフは半推移的 と呼ばれます。^{[ 5 ]}連結された半推移的グラフのうち最小のものは、次数 4 で頂点が 27 個のホルトのグラフです。 ^{[ 1 ] [ 6 ]}紛らわしいことに、一部の著者は「対称グラフ」という用語を、弧推移的グラフではなく、頂点推移的かつ辺推移的なグラフの意味で使用しています。このような定義には半推移的グラフが含まれますが、上記の定義では半推移的グラフは除外されます。

距離推移グラフとは、隣接する頂点のペア（つまり、距離が1離れた頂点）ではなく、同じ距離にある2つの頂点のペアを定義の対象とするグラフです。このようなグラフは、定義により自動的に対称となります。^{[ 1 ]}

t弧はt + 1個の頂点の列として定義され、その列中の連続する2つの頂点は隣接しており、繰り返される頂点は2ステップ以上離れている。t推移グラフは、自己同型群がt弧には推移的に作用するが、( t + 1 ) 弧には作用しないグラフである。1 弧は単なる辺であるため、次数3以上の対称グラフはすべて何らかのtに対してt推移的である必要があり、 tの値を使って対称グラフをさらに分類することができる。例えば、立方体は2 推移的である。 ^{[ 1 ]}

慣例上、「対称グラフ」という用語は「非対称グラフ」という用語を補完するものではないことに注意してください。後者は、非自明な対称性をまったく持たないグラフを指します。

例

任意の頂点数の対称グラフの 2 つの基本的なファミリは、サイクル グラフ(次数 2) と完全グラフです。さらに、正多面体と準正多面体の頂点と辺によって対称グラフが形成されます。立方体、正八面体、二十面体、十二面体、立方八面体、二十十二面体です。立方体を n 次元に拡張すると、ハイパーキューブ グラフ (頂点数が 2 ^{nで次数が n) になります。同様に、八面体を n 次元に拡張すると、}交差多面体のグラフになります。このグラフ ファミリ (頂点数が 2n で次数が 2n − 2) は、カクテル パーティー グラフと呼ばれることもあります。これは、完全マッチングを構成する辺のセットが削除された完全グラフです。頂点数が偶数（2n）である対称グラフの族には、均等分割完全二部グラフK _n,nと、頂点数が2nのクラウングラフがあります。他の多くの対称グラフは巡回グラフに分類できます（ただし、すべてがそうではありません）。

ラドグラフは、頂点数が無限で次数が無限である対称グラフの例です。

立方対称グラフ

対称性条件と、グラフが立方体である（つまり、すべての頂点の次数が3である）という制約を組み合わせると、非常に強い条件が得られ、そのようなグラフはリストに載せられるほど稀です。それらはすべて頂点の数が偶数です。フォスターセンサスとその拡張は、そのようなリストを提供します。^{[ 7 ]}フォスターセンサスは、1930年代にロナルド・M・フォスターがベル研究所に勤務していたときに開始され、^{[ 8 ]} 1988年（フォスターが92歳のとき^{[ 1 ]}）に、当時の最新のフォスターセンサス（512頂点までのすべての立方対称グラフをリストしたもの）が書籍として出版されました。^{[ 9 ]} リストの最初の13項目は、最大30頂点の立方対称グラフです^{[ 10 ] [ 11 ]}（これらのうち10項目は距離推移的でもあります。例外は示されているとおりです）。

頂点	直径	周囲長	グラフ	注釈
4	1	3	完全グラフK 4	距離推移的、2弧推移的
6	2	4	完全二部グラフK 3,3	距離推移、3弧推移
8	3	4	立方体の頂点と辺	距離推移的、2弧推移的
10	2	5	ピーターセングラフ	距離推移、3弧推移
14	3	6	ヒーウッドグラフ	距離推移、4弧推移
16	4	6	メビウス・カントールグラフ	2弧推移
18	4	6	パップスグラフ	距離推移、3弧推移
20	5	5	正十二面体の頂点と辺	距離推移的、2弧推移的
20	5	6	デザルググラフ	距離推移、3弧推移
24	4	6	ナウルグラフ（一般化ピーターセングラフG(12,5)）	2弧推移
26	5	6	F26Aグラフ[ 11 ]	1-弧推移的
28	4	7	コクセターグラフ	距離推移、3弧推移
30	4	8	タット・コクセターグラフ	距離推移、5弧推移

他によく知られている立方対称グラフには、ディクグラフ、フォスターグラフ、ビッグス・スミスグラフがあります。上記の10個の距離推移グラフは、フォスターグラフとビッグス・スミスグラフとともに、唯一の立方距離推移グラフです。

性質

対称グラフの頂点連結性は常に次数dに等しい。[ 3 ]対照^的に、一般に頂点推移グラフでは、頂点連結性は2( d  +1)/3 以下に制限される。^{[ 2 ]}

次数3以上のt推移グラフは、内周が少なくとも2( t −1)である。しかし、 t ≥ 8では、次数3以上の 有限t推移グラフは 存在しない。 次数がちょうど3の場合（立方対称グラフ）、  t  ≥ 6では有限t推移グラフは存在しない。

参照

• 代数的グラフ理論
• 名前付きグラフのギャラリー
• 正則写像

参考文献

1. ビッグス、ノーマン (1993).代数的グラフ理論（第2版）. ケンブリッジ：ケンブリッジ大学出版局. pp.  118– 140. ISBN 0-521-45897-8。
2. ゴッズル、クリス、ロイル、ゴードン(2001).代数的グラフ理論. ニューヨーク: シュプリンガー. p.  59. ISBN 0-387-95220-9。
3. Babai, L (1996). 「自己同型群、同型性、再構成」(PDF) . Graham, R; Grötschel, M ; Lovász, L (編). Handbook of Combinatorics . Elsevier
4. Bouwer, Z. (1970). 「頂点と辺は推移的だが、1-推移的ではないグラフ」 .カナダ数学会報13 (2): 231– 237. doi : 10.4153/CMB-1970-047-8 .
5. Gross, JL & Yellen, J. (2004).グラフ理論ハンドブック. CRC Press. p. 491. ISBN 1-58488-090-2。
6. Holt, Derek F. (1981). 「辺推移的だが弧推移的ではないグラフ」. Journal of Graph Theory . 5 (2): 201– 204. doi : 10.1002/ jgt.3190050210。
7. マーストン・コンダー、「768頂点までの三価対称グラフ」、 J. Combin. Math. Combin. Comput、第20巻、pp. 41–63
8. フォスター、RM「電気ネットワークの幾何学的回路」アメリカ電気学会誌51、309-317、1932年。
9. 「フォスター国勢調査：RMフォスターの連結対称三価グラフ国勢調査」ロナルド・M・フォスター、IZ・バウワー、W・W・チェルノフ、B・モンソン、Z・スター（1988年） ISBN 0-919611-19-2
10. ビッグス、148ページ
11. ワイスタイン、エリック・W.、「立方対称グラフ」、Wolfram MathWorldより

外部リンク

• 立方対称グラフ（フォスター国勢調査）。768頂点までのすべての立方対称グラフと、1000頂点までの一部の立方グラフのデータファイル。Gordon Royle、2001年2月更新、2009年4月18日取得
• 最大10000頂点の三価（立方）対称グラフ。マーストン・コンダー、2011年。