Loading article…
| 自己同型によって定義されるグラフ族 | ||||
|---|---|---|---|---|
| 距離推移 | → | 距離-通常 | ← | 強く規則的な |
| ↓ | ||||
| 対称（弧推移的） | ← | t推移的、 t ≥ 2 | 歪対称 | |
| ↓ | ||||
| （接続されている場合） 頂点および辺が推移的 |
→ | エッジ推移と正規 | → | エッジ推移 |
| ↓ | ↓ | ↓ | ||
| 頂点推移 | → | 通常 | → | （二部構成の場合） 双正則 |
| ↑ | ||||
| ケーリーグラフ | ← | ゼロ対称 | 非対称 | |
数学のグラフ理論の分野において、自己同型とは、辺が辺に、非辺が非辺に写像されるような 頂点の順列である。 [1] グラフが頂点推移グラフであるとは、 Gの任意の2つの頂点v 1とv 2に対して、自己同型fが存在し、
言い換えれば、グラフの自己同型群が 頂点に対して推移的に作用する 場合、そのグラフは頂点推移的である。 [1]グラフが頂点推移的であるのは、そのグラフ補集合が頂点推移的である場合のみであり、これは群の作用が同一であるためである。
孤立した頂点を持たない対称グラフはすべて頂点推移的であり、頂点推移的グラフはすべて正則グラフです。ただし、すべての頂点推移的グラフが対称的であるわけではなく (たとえば、切頂四面体の辺)、すべての正則グラフが頂点推移的であるわけではありません (たとえば、Frucht グラフやTietze のグラフ)。
有限例
有限頂点推移グラフには、対称グラフ（ピーターセングラフ、ヒーウッドグラフ、プラトン立体の頂点と辺など）が含まれます。有限ケイリーグラフ（立方体連結サイクルなど）も頂点推移グラフであり、アルキメデス立体の頂点と辺も同様です（ただし、これらのうち対称なのは2つだけです）。ポトチニク、スピガ、およびベレットは、最大1280の頂点で連結されたすべての立方体頂点推移グラフの国勢調査を構築しました。[2]
すべてのケイリーグラフは頂点推移的ですが、ケイリーグラフではない頂点推移グラフも存在します。最も有名な例はピーターセングラフですが、奇数の頂点次数を持つ辺推移的な非二部グラフの線グラフなど、他のグラフも構築できます。[3]
プロパティ
連結された頂点推移グラフの辺連結性は次数 dに等しく、頂点連結性は少なくとも 2( d + 1)/3となる。 [1] 次数が 4 以下であるか、グラフが辺推移的であるか、グラフが極小ケイリーグラフである場合、頂点連結性もdに等しくなる。[4]
無限の例
無限頂点推移グラフには次のものが含まれます。
- 無限のパス（両方向に無限）
- 無限正則 木、例えば自由群のケーリーグラフ
- 均一なタイル張りのグラフ（平面タイル張りの完全なリストを参照）。これには正多角形によるすべてのタイル張りが含まれます。
- 無限ケーリーグラフ
- ラドーグラフ
2つの可算頂点推移グラフは、その距離関数の比が下からも上からも有界である場合、準等長グラフと呼ばれます。よく知られている予想では、すべての無限頂点推移グラフはケイリーグラフに準等長であるとされています。反例は2001年にDiestelとLeaderによって提案されました。[5] 2005年に、Eskin、Fisher、およびWhyteによって反例が確認されました。[6]
参照
参考文献
- ^ abc Godsil, Chris ; Royle, Gordon (2013) [2001], 代数グラフ理論、Graduate Texts in Mathematics、vol. 207、Springer、ISBN 978-1-4613-0163-9。
- ^ Potočnik P.、Spiga P.、Verret G. (2013)、「最大 1280 頂点の立方頂点推移グラフ」、Journal of Symbolic Computation、50 : 465–477、arXiv : 1201.5317、doi :10.1016/j.jsc.2012.09.002、S2CID 26705221。
- ^ ラウリ、ヨゼフ、スカペラート、ラファエレ (2003)、「グラフ自己同型と再構築に関するトピック」、ロンドン数学会学生テキスト、第 54 巻、ケンブリッジ大学出版局、p. 44、ISBN 0-521-82151-7、MR 1971819Lauri と Scapelleto はこの構築を Mark Watkins に帰しています。
- ^ Babai, L. (1996)、テクニカルレポート TR-94-10、シカゴ大学、2010-06-11 にオリジナルからアーカイブ
- ^ Diestel, Reinhard; Leader, Imre (2001)、「非ケイリーグラフの限界に関する予想」(PDF)、Journal of Algebraic Combinatorics、14 (1): 17–25、doi : 10.1023/A:1011257718029、S2CID 10927964。
- ^ Eskin, Alex; Fisher, David; Whyte, Kevin (2005). 「可解群の準等長変換と剛性」. arXiv : math.GR/0511647 .。
外部リンク
- Weisstein、Eric W.「頂点推移グラフ」。MathWorld。
- 小さな連結立方頂点推移グラフの国勢調査。Primož Potočnik、Pablo Spiga、Gabriel Verret、2012 年。
- 48 個未満の頂点の頂点推移グラフ。Gordon Royle と Derek Holt、2020 年。