距離推移グラフ

数学の分野であるグラフ理論において、距離推移グラフとは、任意の距離iにある任意の 2 つの頂点 vとw 、および同じ距離にある他の任意の 2 つの頂点xとy が与えられたときに、 vからxへ、wからyへ 移るグラフの自己同型が存在するグラフのことである。距離推移グラフは、1971 年にNorman L. Biggsと DH Smith によって初めて定義されました。

距離推移グラフが興味深いのは、大きな自己同型群を持つためです。興味深い有限群には、距離推移グラフの自己同型群、特に直径が 2 であるものなどがあります。

距離推移グラフのファミリーの最初の例としては、次のものがあります。

• ジョンソングラフ。
• グラスマングラフ。
• ハミンググラフ（ハイパーキューブグラフを含む）。
• 折りたたまれた立方体グラフ。
• スクエアルークのグラフ。
• リビングストングラフ。

1971 年にビッグスとスミスが発表した後、有限連結された三価距離推移グラフは 12 個しかないことが示されました。これらは次のとおりです。

すべての距離推移グラフは距離正則ですが、その逆は必ずしも真ではありません。

1969年、ビッグス・スミスの定義が発表される前に、ゲオルギー・アデルソン＝ヴェルスキー率いるロシアのグループは、距離正則だが距離推移的ではないグラフが存在することを示した。距離推移的ではない最小の距離正則グラフは、頂点が16個で次数が6のシュリカンデグラフである。次数が3のこのタイプのグラフは、頂点が126個のトゥッテ12ケージのみである。距離推移グラフの完全なリストは、3より大きい次数については知られているが、任意の大きな頂点次数を持つ距離推移グラフの分類は未解決のままである。

初期の作品

• Adel'son-Vel'skii, GM ; Veĭsfeĭler, B. Ju. ; Leman, AA; Faradžev, IA (1969)、「自己同型の推移群を持たないグラフの例」、Doklady Akademii Nauk SSSR、185 : 975–976、MR  0244107。
• ビッグス、ノーマン (1971)、「線形グラフの交差行列」、組合せ数学とその応用 (Proc. Conf.、オックスフォード、1969)、ロンドン: アカデミック プレス、pp. 15–23、MR  0285421。
• ビッグス、ノーマン (1971)、「自己同型性の有限群」、ロンドン数学会講義ノートシリーズ、第 6 巻、ロンドンおよびニューヨーク: ケンブリッジ大学出版局、MR  0327563。
• Biggs, NL; Smith, DH (1971)、「三価グラフについて」、ロンドン数学会誌、3 (2): 155–158、doi :10.1112/blms/3.2.155、MR  0286693。
• スミス、DH (1971)、「原始グラフと非原始グラフ」、四半期数学ジャーナル、第2シリーズ、22 (4): 551–557、doi :10.1093/qmath/22.4.551、MR  0327584。

調査

• Biggs, NL (1993)、「距離推移グラフ」、代数グラフ理論(第 2 版)、ケンブリッジ大学出版局、pp. 155–163、第20章。
• ヴァン・ボン、ジョン（2007）、「有限原始距離推移グラフ」、ヨーロッパ組合せ論ジャーナル、28（2）：517–532、doi：10.1016/j.ejc.2005.04.014、MR  2287450。
• Brouwer, AE ; Cohen, AM; Neumaier, A. (1989)、「距離推移グラフ」、距離正則グラフ、ニューヨーク: Springer-Verlag、pp. 214–234、第7章。
• Cohen, AM Cohen (2004)、「距離推移グラフ」、Beineke, LW; Wilson, RJ (編)、代数グラフ理論のトピック、数学とその応用百科事典、第 102 巻、ケンブリッジ大学出版、pp. 222–249。
• Godsil, C. ; Royle, G. (2001)、「距離推移グラフ」、代数グラフ理論、ニューヨーク: Springer-Verlag、pp. 66–69、セクション4.5。
• Ivanov, AA (1992)、「距離推移グラフとその分類」、Faradžev, IA、Ivanov, AA、Klin, M.、他編『組合せオブジェクトの代数理論』、Math. Appl. (Soviet Series)、第 84 巻、ドルドレヒト: Kluwer、pp. 283–378、MR  1321634。

• Weisstein、Eric W.「距離推移グラフ」。MathWorld。