対称グラフ
数学のグラフ理論の分野において、あるグラフ G が対称グラフ（たいしょうぐらふ、英: symmetric graph）あるいは弧推移グラフであるとは、G に含まれる任意の与えられた隣接する頂点同士からなるペア u1—v1 および u2—v2 に対して、
- f(u1) = u2 and f(v1) = v2 [1]
であるような自己同型
- f : V(G) → V(G)
が存在することを言う。言い換えると、グラフが対称的であるとは、その自己同型群が、向き付けられた隣接する頂点同士のペアの上（すなわち、方向を持つと考えられる辺の上）で推移的に作用することを言う[2]。 そのようなグラフはしばしば1-弧推移的[2]（1-arc-transitive）あるいは旗推移的[3]（flag-transitive）とも呼ばれる。
定義に従い（u1 と u2 を無視することで）、孤立頂点を含まない対称グラフは必ず頂点推移的でなければならないことが分かる[1]。また、上述の定義では、一つの辺を別のものへと写しているため、対称グラフは辺推移的でなければならないことも分かる。しかしながら、辺推移グラフは必ずしも対称グラフではない。なぜならば、a—b が d—c ではなく c—d へと写されることも考えられるからである。また、例えば、半対称グラフは辺推移的かつ正則であるが、頂点推移的ではない。
したがって、全ての連結対称グラフは頂点推移的かつ辺推移的であり、次数が奇数であるようなグラフに対してはその逆も成立する[3]。しかしながら、次数が偶数である場合は、頂点推移的かつ辺推移的であるが、対称でないような連結グラフも存在する[4]。そのようなグラフは半推移的（half-transitive）であると呼ばれる[5]。最小の連結半推移グラフは、次数4で頂点数27のホルトグラフである[1][6]。厄介なことに、学者の中には対称グラフという語を、弧推移グラフではなく、頂点推移的かつ辺推移的であるようなグラフに対して用いる人もいる。そのような定義では、上述の定義では除外されている半推移グラフを含むことになる。
距離推移グラフでは、隣接している頂点同士のペア（すなわち、距離が1だけ離れている頂点のペア）を考える代わりに、各々が同じ距離だけ離れているペアを考える。そのようなグラフは、定義より、自然に対称グラフとなる[1]。
t-弧という語が、「t + 1 個の頂点からなる列で、その列において連続するどの二つの頂点も必ずグラフ上で隣接し、かつ繰り返し現れる頂点については必ず二段階以上離れているもの」に対して定義される。t-推移グラフとは、その自己同型群がt-弧の上では推移的に作用するが (t+1)-弧の上ではそのように作用しないグラフのことを言う。1-弧は単純に辺であるため、次数が3以上であるような全ての対称グラフには、t-推移的となるような t が必ず存在し、そのような t の値は対称グラフを分類する際に用いられる。例えば、立方体は2-推移的である[1]。
例 編集
対称性の条件と、グラフが立方体型（すなわち、すべての頂点の次数が3）であるという制限を組み合わせることは、条件として十分強く、そのようなグラフはリスト化出来るほど特徴的なものである。フォスター調査（Foster census）とその追加調査では、そのようなリストが提供された[7]。フォスター調査は、1930年代にロナルド・フォスターによって、彼がベル研究所に雇われていた頃に開始された[8]。また、1988年（フォスターはこの時92歳であった[1]）に、最新フォスター調査（512個の頂点を含むものまでの全ての立方体対称グラフをリスト化した）が、書籍の形式で出版された[9]。その初めの13個の項目は、30の頂点を含むものまでの立方体対称グラフである[10][11]（その内の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 | F26Aグラフ[11] | 1-推移的 |
| 28 | 4 | 7 | コクセターグラフ | 距離推移的、3-推移的 |
| 30 | 4 | 8 | トゥッテ-コクセターグラフ | 距離推移的、5-推移的 |
この他のよく知られた立方体対称グラフには、ディックグラフ、フォスターグラフやビッグス-スミスグラフがある。上のリスト内の10個の距離推移グラフと、フォスターグラフおよびビッグス-スミスグラフのみが、立方体距離推移グラフである。
立方体型でない対称グラフには、（次数2の）閉路グラフや、（頂点の数が5以上の場合には次数が4以上の）完全グラフ、（頂点の数が16以上の場合には次数が4以上の）超立方体グラフ、および正八面体、正二十面体、立方八面体、二十・十二面体のそれぞれの頂点と辺からなるグラフが挙げられる。無限個の頂点と無限大の次数を持つ対称グラフの例として、ラドグラフが挙げられる。
性質 編集
対称グラフの頂点連結度は、常に次数 d に等しい[3]。対称的に、頂点推移グラフの頂点連結度は一般的には 2(d+1)/3 より小さい[2]。
次数 3 以上の t-推移グラフの内周は少なくとも 2(t–1) である。しかし、t ≥ 8 に対しては、次数 3 以上の有限な t-推移グラフというものは存在しない。次数がちょうど 3 である場合（立方体対称グラフ）には、t ≥ 6 に対して、そのようなグラフは存在しない。
参考文献 編集
- ^ a b c d e f Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge: Cambridge University Press. pp. 118–140. ISBN 0-521-45897-8
- ^ a b c Godsil, Chris; Royle, Gordon (2001). Algebraic Graph Theory. New York: Springer. p. 59. ISBN 0-387-95220-9
- ^ a b c Babai, L (1996). “Automorphism groups, isomorphism, reconstruction”. In Graham, R; Groetschel, M; Lovasz, L. Handbook of Combinatorics. Elsevier
- ^ Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.
- ^ Gross, J.L. and Yellen, J. (2004). Handbook of Graph Theory. CRC Press. p. 491. ISBN 1-58488-090-2
- ^ Holt, Derek F. (1981). “A graph which is edge transitive but not arc transitive”. Journal of Graph Theory 5 (2): 201–204. doi:10.1002/jgt.3190050210..
- ^ Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63
- ^ Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.
- ^ "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
- ^ Biggs, p. 148
- ^ a b Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.
関連項目 編集
外部リンク 編集
- 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.