距離推移グラフ
数学のグラフ理論の分野における距離推移グラフ(きょりすいいグラフ、英: distance-transitive graph)とは、任意の距離 i だけ離れた任意の二頂点 v と w と、同じ距離だけ離れた他の任意の二頂点 x と y との間に自己同型(英語版)(v を x へ、w を y へ写すようなもの)が存在するグラフのことを言う。
距離推移グラフは頂点推移的、対称かつ距離正則(英語版)である。
距離推移グラフの興味深い点の一つに、それが大きな自己同型群を持つ、というものがある。いくつかの興味深い有限群は、特に直径が 2 であるような距離推移グラフの自己同型群である。
距離推移グラフは、ノルマン・L・ビッグス(英語版)と D・H・スミスによって 1971年に初めて定義された。彼らは、有限3価(trivalent)な距離推移グラフは 12 種類しか存在しないことを証明した。それらを、次に挙げる: