数学のグラフ理論の分野における距離推移グラフ（きょりすいいグラフ、）とは、任意の距離 i だけ離れた任意の二頂点 v と w と、同じ距離だけ離れた他の任意の二頂点 x と y との間に（v を x へ、w を y へ写すようなもの）が存在するグラフのことを言う。
距離推移グラフは頂点推移的、対称かつである。
距離推移グラフの興味深い点の一つに、それが大きな自己同型群を持つ、というものがある。いくつかの興味深い有限群は、特に直径が 2 であるような距離推移グラフの自己同型群である。
距離推移グラフは、と Ｄ・Ｈ・スミスによって 1971年に初めて定義された。彼らは、有限3価（trivalent）な距離推移グラフは 12 種類しか存在しないことを証明した。それらを、次に挙げる： グラフ名 頂点数 直径 内周 完全グラフ K4 4 1 3 {3;1} 完全2部グラフ K3,3 6 2 4 {3,2;1,3} ピーターセングラフ 10 2 5 {3,2;1,1} 立方体のグラフ 8 3 4 {3,2,1;1,2,3} ヒーウッドグラフ 14 3 6 {3,2,2;1,1,3} 18 4 6 {3,2,2,1;1,1,2,3} 28 4 7 {3,2,2,1;1,1,1,2} 30 4 8 {3,2,2,2;1,1,1,3} 正十二面体のグラフ 20 5 5 {3,2,1,1,1;1,1,1,2,3} 20 5 6 {3,2,2,1,1;1,1,2,2,3} 102 7 9 {3,2,2,2,1,1,1;1,1,1,1,1,1,3} 90 8 10 {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
1969年、の率いるロシアのグループが、であるが距離推移的でないグラフが存在することを、独自に示した。そのようなタイプのグラフの内、次数が 3 であるような唯一つのものは、126-頂点のである。距離推移的でないような最小の距離正則グラフは、（Shrikhande graph）である。3よりも大きい幾つかの次数に対しては、距離推移グラフの完全なリストは知られている。しかし、任意の大きさの頂点次数に対する距離推移グラフの分類については、未解決となっている。
最も簡単な、距離推移グラフの例である族は、である。その他の族には、folded cube graphや、正方がある。これら三つの族は全て、任意に高い次数を持つ。
参考文献 初期の結果 . . . . .
調査 , chapter 20. . , chapter 7. . , section 4.5. .
外部リンク