対称グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
ピーターセングラフ立体英語版対称グラフである。隣接している頂点同士からなるどのようなペアも、自己同型英語版によって他のペアへと写すことが出来る。なぜならば、任意の5-頂点リングはどのような別のものへも写され得るからである。

数学グラフ理論の分野において、あるグラフ G対称グラフ(たいしょうぐらふ、: symmetric graph)あるいは弧推移グラフであるとは、G に含まれる任意の与えられた隣接する頂点同士からなるペア u1v1 および u2v2 に対して、

f(u1) = u2 and f(v1) = v2 [1]

であるような自己同型英語版

f : V(G) → V(G)

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

定義に従い(u1u2 を無視することで)、孤立頂点を含まない対称グラフは必ず頂点推移的でなければならないことが分かる[1]。また、上述の定義では、一つの辺を別のものへと写しているため、対称グラフは辺推移的でなければならないことも分かる。しかしながら、辺推移グラフは必ずしも対称グラフではない。なぜならば、abdc ではなく cd へと写されることも考えられるからである。また、例えば、半対称グラフは辺推移的かつ正則であるが、頂点推移的ではない。

したがって、全ての連結対称グラフは頂点推移的かつ辺推移的であり、次数が奇数であるようなグラフに対してはその逆も成立する[3]。しかしながら、次数が偶数である場合は、頂点推移的かつ辺推移的であるが、対称でないような連結グラフも存在する[4]。そのようなグラフは半推移的英語版(half-transitive)であると呼ばれる[5]。最小の連結半推移グラフは、次数4で頂点数27のホルトグラフ英語版である[1][6]。厄介なことに、学者の中には対称グラフという語を、弧推移グラフではなく、頂点推移的かつ辺推移的であるようなグラフに対して用いる人もいる。そのような定義では、上述の定義では除外されている半推移グラフを含むことになる。

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

t-弧という語が、「任意の連続した頂点が隣接しているような頂点の列 t+1 および2ステップ以上離れているような繰り返された頂点」に対して定義される。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 に対して、そのようなグラフは存在しない。

関連項目[編集]

参考文献[編集]

  1. ^ 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. 
  2. ^ a b c Godsil, Chris; Royle, Gordon (2001). Algebraic Graph Theory. New York: Springer. p. 59. ISBN 0-387-95220-9. 
  3. ^ a b c Babai, L (1996). “Automorphism groups, isomorphism, reconstruction”. In Graham, R; Groetschel, M; Lovasz, L. Handbook of Combinatorics. Elsevier. http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps. 
  4. ^ Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.
  5. ^ Gross, J.L. and Yellen, J. (2004). Handbook of Graph Theory. CRC Press. p. 491. ISBN 1-58488-090-2. 
  6. ^ 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. .
  7. ^ Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63
  8. ^ Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.
  9. ^ "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
  10. ^ Biggs, p. 148
  11. ^ a b Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.

外部リンク[編集]