頂点推移グラフ
数学のグラフ理論の分野における頂点推移グラフ(ちょうてんすいいグラフ、英: vertex-transitive graph)とは、与えられた任意の二頂点 v1 および v2 に対して
f ( v 1 ) = v 2 {\displaystyle f(v_{1})=v_{2}\ }
であるような自己同型(英語版)
f : V ( G ) → V ( G ) {\displaystyle f:V(G)\rightarrow V(G)\ }
が存在するグラフ G のことを言う。
言い換えれば、グラフが頂点推移的であるとは、その自己同型群が各頂点の上で可移的(transitively)に作用することを言う。グラフが頂点推移的であるための必要十分条件は、その補グラフが頂点推移的であることである(なぜならば、それらの群作用は等しいため)。
孤立頂点を含まない対称グラフは、頂点推移的である。また、頂点推移グラフは正則である。しかし、すべての頂点推移グラフが対称であるとは限らない(例えば、切頂四面体の辺から成るグラフ)。また、すべての正則グラフが頂点推移的であるとは限らない(例えば、フルフトグラフ(英語版))。