対称グラフ

数学のグラフ理論の分野において、あるグラフ G が対称グラフ（たいしょうぐらふ、）あるいは弧推移グラフであるとは、G に含まれる任意の与えられた隣接する頂点同士からなるペア u1—v1 および u2—v2 に対して、

f(u1) = u2 and f(v1) = v2 

であるような

f : V(G) → V(G)

が存在することを言う。言い換えると、グラフが対称的であるとは、その自己同型群が、向き付けられた隣接する頂点同士のペアの上（すなわち、方向を持つと考えられる辺の上）で推移的に作用することを言う。 
そのようなグラフはしばしば1-弧推移的（1-arc-transitive）あるいは旗推移的（flag-transitive）とも呼ばれる。

定義に従い（u1 と u2 を無視することで）、孤立頂点を含まない対称グラフは必ず頂点推移的でなければならないことが分かる。また、上述の定義では、一つの辺を別のものへと写しているため、対称グラフは辺推移的でなければならないことも分かる。しかしながら、辺推移グラフは必ずしも対称グラフではない。なぜならば、a—b が d—c ではなく c—d へと写されることも考えられるからである。また、例えば、半対称グラフは辺推移的かつ正則であるが、頂点推移的ではない。

したがって、全ての連結対称グラフは頂点推移的かつ辺推移的であり、次数が奇数であるようなグラフに対してはその逆も成立する。しかしながら、次数が偶数である場合は、頂点推移的かつ辺推移的であるが、対称でないような連結グラフも存在するBouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.。そのようなグラフは（half-transitive）であると呼ばれる。最小の連結半推移グラフは、次数4で頂点数27のである.。厄介なことに、学者の中には対称グラフという語を、弧推移グラフではなく、頂点推移的かつ辺推移的であるようなグラフに対して用いる人もいる。そのような定義では、上述の定義では除外されている半推移グラフを含むことになる。

距離推移グラフでは、隣接している頂点同士のペア（すなわち、距離が1だけ離れている頂点のペア）を考える代わりに、各々が同じ距離だけ離れているペアを考える。そのようなグラフは、定義より、自然に対称グラフとなる。

t-弧という語が、「 個の頂点からなる列で、その列において連続するどの二つの頂点も必ずグラフ上で隣接し、かつ繰り返し現れる頂点については必ず二段階以上離れているもの」に対して定義される。t-推移グラフとは、その自己同型群がt-弧の上では推移的に作用するが (t+1)-弧の上ではそのように作用しないグラフのことを言う。1-弧は単純に辺であるため、次数が3以上であるような全ての対称グラフには、t-推移的となるような t が必ず存在し、そのような t の値は対称グラフを分類する際に用いられる。例えば、立方体は2-推移的である。

 例 
対称性の条件と、グラフが立方体型（すなわち、すべての頂点の次数が3）であるという制限を組み合わせることは、条件として十分強く、そのようなグラフはリスト化出来るほど特徴的なものである。フォスター調査（Foster census）とその追加調査では、そのようなリストが提供されたMarston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63。フォスター調査は、1930年代にによって、彼がベル研究所に雇われていた頃に開始されたFoster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.。また、1988年（フォスターはこの時92歳であった）に、最新フォスター調査（512個の頂点を含むものまでの全ての立方体対称グラフをリスト化した）が、書籍の形式で出版された"The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2。その初めの13個の項目は、30の頂点を含むものまでの立方体対称グラフであるBiggs, p. 148Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.（その内の10個はまた距離推移的である。例外も以下に示されている）：

頂点    内周  グラフ  注釈4  1  3  完全グラフ K4  距離推移的、2-推移的6  2  4  完全2部グラフ K3,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    1-推移的28  4  7    距離推移的、3-推移的30  4  8    距離推移的、5-推移的

この他のよく知られた立方体対称グラフには、、やがある。上のリスト内の10個の距離推移グラフと、およびのみが、立方体距離推移グラフである。

立方体型でない対称グラフには、（次数2の）閉路グラフや、（頂点の数が5以上の場合には次数が4以上の）完全グラフ、（頂点の数が16以上の場合には次数が4以上の）、および正八面体、正二十面体、立方八面体、二十・十二面体のそれぞれの頂点と辺からなるグラフが挙げられる。無限個の頂点と無限大の次数を持つ対称グラフの例として、が挙げられる。

 性質 
対称グラフの頂点連結度は、常に次数 d に等しい。対称的に、頂点推移グラフの頂点連結度は一般的には 2(d+1)/3 より小さい。

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

 参考文献 

 関連項目 
代数的グラフ理論
名称のあるグラフのギャラリー

 外部リンク 
Cubic symmetric graphs (The Foster Census). Data files for all cubic symmetric graphs up to 768 vertices, and some cubic graphs with up to 1000 vertices. Gordon Royle, updated February 2001, retrieved 2009-04-18.
Trivalent (cubic) symmetric graphs on up to 2048 vertices. Marston Conder, August 2006, retrieved 2009-08-20.

Category:グラフ理論のグラフ
Category:数学に関する記事
Category:代数的グラフ理論