頂点推移グラフのソースを表示

[[数学]]の[[グラフ理論]]の分野における'''頂点推移グラフ'''（ちょうてんすいいグラフ、{{Lang-en-short|vertex-transitive graph}}）とは、与えられた任意の二頂点 v<sub>1</sub> および v<sub>2</sub> に対して
:<math>f(v_1) = v_2\ </math>
であるような{{仮リンク|グラフ自己同型性|label=自己同型|en|graph automophism}}
:<math>f:V(G) \rightarrow V(G)\ </math>
が存在する[[グラフ理論|グラフ]] ''G'' のことを言う。

言い換えれば、グラフが頂点推移的であるとは、その自己同型群が各頂点の上で[[群作用|可移的（transitively）に作用する]]ことを言う<ref>{{citation|first1=Chris|last1=Godsil|authorlink1=:en:Chris Godsil|first2=Gordon|last2=Royle|authorlink2=:en:Gordon Royle|title=Algebraic Graph Theory|series=Graduate Texts in Mathematics|volume=207|publisher=Springer-Verlag|location=New York|year=2001}}.</ref>。グラフが頂点推移的であるための[[必要十分条件]]は、その[[補グラフ]]が頂点推移的であることである（なぜならば、それらの群作用は等しいため）。

孤立頂点を含まない[[対称グラフ]]は、頂点推移的である。また、頂点推移グラフは[[正則グラフ|正則]]である。しかし、すべての頂点推移グラフが対称であるとは限らない（例えば、[[切頂四面体]]の辺から成るグラフ）。また、すべての正則グラフが頂点推移的であるとは限らない（例えば、{{仮リンク|フルフトグラフ|en|Frucht graph}}）。

== 有限の例 ==
[[Image:TruncatedTetrahedron.gif|thumb|right|220px|[[切頂四面体]]の辺から成るグラフは、頂点推移的である（[[ケイリーグラフ]]でもある）が、[[対称グラフ|対称]]でない。]]
[[対称グラフ]]（例えば、[[ピーターセングラフ]]、[[ヒーウッドグラフ]]、[[正多面体]]の頂点と辺から成るグラフなど）であれば、有限の頂点推移グラフである。有限の[[ケイリーグラフ]]（例えば、{{仮リンク|キューブ連結サイクル|en|cube-connected cycles}}など）もまた、頂点推移的である。なぜならば、それは[[半正多面体]]の頂点と辺から成るため（それらのうち対称であるものは二つしかないが）である。Poto&#269;nik、Spiga および Verret は、最大 1280 個の頂点を含む全ての連結立体頂点推移グラフの調査を行った<ref>{{citation|title=Cubic vertex-transitive graphs on up to 1280 vertices|author=Poto&#269;nik P., Spiga P. and Verret G.|year=2012|publisher=Journal of Symbolic Computation}}.</ref>。

== 性質 ==
頂点推移グラフの{{仮リンク|連結度|label=辺連結度|en|Connectivity (graph theory)}}は、その[[正則グラフ|次数]] ''d'' に等しい。一方、その{{仮リンク|連結度|label=頂点連結度|en|Connectivity (graph theory)}}は少なくとも 2(''d''+1)/3 である<ref>{{Citation|title=Algebraic Graph Theory|author=Godsil, C. and Royle, G.|year=2001|publisher=Springer Verlag}}</ref>。そのグラフの次数が 4 以下であるか、グラフが[[辺推移グラフ|辺推移的]]であるか、あるいは最小の[[ケイリーグラフ]]であるなら、その頂点連結度も次数 ''d'' と等しくなる<ref>{{Citation|title=Technical Report TR-94-10|author=Babai, L.|year=1996|publisher=University of Chicago}}[http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps]</ref>。

== 無限の例 ==
無限な頂点推移グラフは次を含む:
* 無限[[グラフ理論|路]]（両方向に無限）
* 無限[[正則グラフ|正則]][[木 (数学)|木]]。例えば、[[自由群]]の[[ケイリーグラフ]]
* {{仮リンク|正多角形によるタイル張り|en|Tiling by regular polygons}}を含む、{{仮リンク|平面一様充填|en|uniform tessellation}}のグラフ（[[平面充填]]の{{仮リンク|凸一様タイル張りの一覧|label=一覧|en|List of convex uniform tilings}}を参照されたい）
* 無限[[ケイリーグラフ]]
* {{仮リンク|ラドグラフ|en|Rado graph}}
二つの[[可算]]な頂点推移グラフが[[準等距離同型]]（quasi-isometric）であるとは、それらの[[距離函数]]の比が上下ともに有界であることを言う。有名な予想に、全ての無限な頂点推移グラフは[[ケイリーグラフ]]と準等距離同型である、というものがあったが、その反例は[[リチャード・ディエステル|ディエステル]]と{{仮リンク|イムレ・リーダー|label=リーダー|en|Imre Leader}}によって提唱され<ref>{{citation|first1=Reinhard|last1=Diestel|first2=Imre|last2=Leader|authorlink2=:en:Imre Leader|url=http://www.math.uni-hamburg.de/home/diestel/papers/Cayley.pdf|title=A conjecture concerning a limit of non-Cayley graphs|journal=Journal of Algebraic Combinatorics|volume=14|issue=1|year=2001|pages=17–25|doi=10.1023/A:1011257718029}}.</ref>、近年、エスキン、フィッシャーおよびホワイトによってその確証が得られた<ref>{{cite arxiv|first1=Alex|last1=Eskin|first2=David|last2=Fisher|first3=Kevin|last3=Whyte|eprint=math.GR/0511647 |title=Quasi-isometries and rigidity of solvable groups|year=2005}}.</ref>。

== 関連項目 ==
* [[辺推移グラフ]]
* {{仮リンク|ロヴァース予想|en|Lovász conjecture}}
* [[半対称グラフ]]

== 参考文献 ==
<references/>

== 外部リンク ==
*[http://www.matapp.unimib.it/~spiga/index.html A census of small connected cubic vertex-transitive graphs ]. Primo&#382; Poto&#269;nik, Pablo Spiga, Gabriel Verret, 2012.

{{DEFAULTSORT:ちようてんすいいくらふ}}

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