Wikipedia

距離推移グラフ

数学のグラフ理論の分野における距離推移グラフ（きょりすいいグラフ、英: distance-transitive graph）とは、任意の距離 i だけ離れた任意の二頂点 v と w と、同じ距離だけ離れた他の任意の二頂点 x と y との間に自己同型（英語版）（v を x へ、w を y へ写すようなもの）が存在するグラフのことを言う。

最大の3-正則距離推移グラフであるビッグス-スミスグラフ（英語版）

距離推移グラフは頂点推移的、対称かつ距離正則（英語版）である。

距離推移グラフの興味深い点の一つに、それが大きな自己同型群を持つ、というものがある。いくつかの興味深い有限群は、特に直径が 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-頂点のトゥッテ12-ケージ（英語版）である。距離推移的でないような最小の距離正則グラフは、シュリクハンデグラフ（英語版）（Shrikhande graph）である。3よりも大きい幾つかの次数に対しては、距離推移グラフの完全なリストは知られている。しかし、任意の大きさの頂点次数に対する距離推移グラフの分類については、未解決となっている。

最も簡単な、距離推移グラフの例である漸近（英語版）族は、超立方体グラフ（英語版）である。その他の族には、folded cube graphや、正方ルークのグラフ（英語版）がある。これら三つの族は全て、任意に高い次数を持つ。

参考文献

編集

初期の結果

  • Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju.; Leman, A. A.; Faradžev, I. A. (1969), “An example of a graph which has no transitive group of automorphisms”, Doklady Akademii Nauk SSSR 185: 975–976, MR0244107 .
  • Biggs, Norman (1971), “Intersection matrices for linear graphs”, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 15–23, MR0285421 .
  • Biggs, Norman (1971), Finite Groups of Automorphisms, London Mathematical Society Lecture Note Series, 6, London & New York: Cambridge University Press, MR0327563 .
  • Biggs, N. L.; Smith, D. H. (1971), “On trivalent graphs”, Bulletin of the London Mathematical Society 3 (2): 155–158, doi:10.1112/blms/3.2.155, MR0286693 .
  • Smith, D. H. (1971), “Primitive and imprimitive graphs”, The Quarterly Journal of Mathematics. Oxford. Second Series 22 (4): 551–557, doi:10.1093/qmath/22.4.551, MR0327584 .

調査

  • Biggs, N. L. (1993), “Distance-Transitive Graphs”, Algebraic Graph Theory (2nd ed.), Cambridge University Press, pp. 155–163 , chapter 20.
  • Van Bon, John (2007), “Finite primitive distance-transitive graphs”, European Journal of Combinatorics 28 (2): 517–532, doi:10.1016/j.ejc.2005.04.014, MR2287450 .
  • Brouwer, A. E.; Cohen, A. M.; Neumaier, A. (1989), “Distance-Transitive Graphs”, Distance-Regular Graphs, New York: Springer-Verlag, pp. 214–234 , chapter 7.
  • Cohen, A. M. Cohen (2004), “Distance-transitive graphs”, in Beineke, L. W.; Wilson, R. J., Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, 102, Cambridge University Press, pp. 222–249 .
  • Godsil, C.; Royle, G. (2001), “Distance-Transitive Graphs”, Algebraic Graph Theory, New York: Springer-Verlag, pp. 66–69 , section 4.5.
  • Ivanov, A. A. (1992), “Distance-transitive graphs and their classification”, in Faradžev, I. A.; Ivanov, A. A.; Klin, M. et al., The Algebraic Theory of Combinatorial Objects, Math. Appl. (Soviet Series), 84, Dordrecht: Kluwer, pp. 283–378, MR1321634 .

外部リンク

編集
「https://ja.wikipedia.org/w/index.php?title=距離推移グラフ&oldid=81485759」から取得