About: 距離推移グラフ

数学のグラフ理論の分野における距離推移グラフ（きょりすいいグラフ、英: distance-transitive graph）とは、任意の距離 i だけ離れた任意の二頂点 v と w と、同じ距離だけ離れた他の任意の二頂点 x と y との間に（v を x へ、w を y へ写すようなもの）が存在するグラフのことを言う。 距離推移グラフは頂点推移的、対称かつである。 距離推移グラフの興味深い点の一つに、それが大きな自己同型群を持つ、というものがある。いくつかの興味深い有限群は、特に直径が 2 であるような距離推移グラフの自己同型群である。 距離推移グラフは、と Ｄ・Ｈ・スミスによって 1971年に初めて定義された。彼らは、有限3価（trivalent）な距離推移グラフは 12 種類しか存在しないことを証明した。それらを、次に挙げる： 1969年、の率いるロシアのグループが、であるが距離推移的でないグラフが存在することを、独自に示した。そのようなタイプのグラフの内、次数が 3 であるような唯一つのものは、126-頂点のである。距離推移的でないような最小の距離正則グラフは、（Shrikhande graph）である。3よりも大きい幾つかの次数に対しては、距離推移グラフの完全なリストは知られている。しかし、任意の大きさの頂点次数に対する距離推移グラフの分類については、未解決となっている。