Loading article…
| 自己同型によって定義されるグラフ族 | ||||
|---|---|---|---|---|
| 距離推移 | → | 距離-通常 | ← | 強く規則的な |
| ↓ | ||||
| 対称的（弧推移的） | ← | t推移的、 t ≥ 2 | 歪対称 | |
| ↓ | ||||
| （接続されている場合） 頂点および辺が推移的 |
→ | エッジ推移と正規 | → | エッジ推移 |
| ↓ | ↓ | ↓ | ||
| 頂点推移 | → | 通常 | → | （二部構成の場合） 双正則 |
| ↑ | ||||
| ケーリーグラフ | ← | ゼロ対称 | 非対称 | |
数学のグラフ理論の分野において、ゼロ対称グラフとは、各頂点がちょうど3つの接続辺を持ち、2つの頂点ごとに、一方の頂点から他方の頂点に向かう唯一の対称性が存在する連結グラフである。このようなグラフは頂点推移グラフであるが、辺推移グラフにはならない。対称性の数は頂点の数に等しく、すべての辺を他のすべての辺に向かうには少なすぎる。[1]
このグラフのクラスの名前は、1966年にRMフォスターがHSMコクセターに宛てた手紙の中 で作ったものです。[2]群論の文脈では、ゼロ対称グラフは対称群のグラフィカル正規表現とも呼ばれます。[3]
例
最小のゼロ対称グラフは18頂点を持つ非平面グラフである。[4]そのLCF表記は[5,−5] 9である。
平面グラフの中でも、切頂立方八面体グラフと切頂二十六面体グラフもゼロ対称性を持つ。[5]
これらの例はすべて二部グラフです。しかし、二部ではないゼロ対称グラフのより大きな例も存在します。[6]
これらの例には、3つの異なる対称性クラス（軌道）の辺も存在します。ただし、2つの軌道の辺のみを持つゼロ対称グラフも存在します。そのような最小のグラフは20の頂点を持ち、LCF表記は[6,6,-6,-6] 5です。[7]
プロパティ
すべての有限ゼロ対称グラフはケイリーグラフである。この特性は、一般的には立方頂点推移グラフには必ずしも当てはまらないが、ゼロ対称グラフに関する組合せ列挙タスクの解決に役立つ。最大1280頂点のゼロ対称グラフは97687個ある。これらのグラフは、立方ケイリーグラフの89%と、同じ数の頂点に接続されたすべての頂点推移立方グラフの88%を占める。[8]
既知の有限連結ゼロ対称グラフはすべてハミルトン閉路を含むが、すべての有限連結ゼロ対称グラフが必ずハミルトンであるかどうかは不明である。[9]これは、（ゼロ対称ではない5つの例外を除いて）すべての有限連結頂点推移グラフとすべての有限ケイリーグラフはハミルトンであるというロヴァース予想の特殊なケースである。
参照
- 半対称グラフ、2 つの辺の間には対称性があるが、2 つの頂点の間には対称性がないグラフ (ゼロ対称グラフの定義における辺と頂点の役割を逆にする)
参考文献
- ^ コクセター、ハロルド・スコット・マクドナルド;フルクト、ロベルト; パワーズ、デビッド・L. (1981)、ゼロ対称グラフ、Academic Press、Inc. [Harcourt Brace Jovanovich、出版社]、ニューヨーク・ロンドン、ISBN 0-12-194580-4、MR 0658666
- ^ Coxeter、Frucht & Powers (1981)、p. ix.
- ^ ラウリ、ヨゼフ、スカペラート、ラファエレ (2003)、「グラフの自己同型性と再構築に関するトピック」、ロンドン数学会学生用テキスト、ケンブリッジ大学出版局、p. 66、ISBN 9780521529037。
- ^ Coxeter、Frucht & Powers (1981)、図 1.1、p. 5.
- ^ Coxeter、Frucht & Powers (1981)、75 および 80 ページ。
- ^ Coxeter、Frucht & Powers (1981)、p. 55.
- ^ デラウェア州マーストン、コンドル; Pisanski, トマジュ; Žitnik、Arjana (2017)、「頂点推移グラフとその弧の種類」、Ars Mathematica Contemporanea、12 (2): 383–413、arXiv : 1505.02029、doi :10.26493/1855-3974.1146.f96、MR 3646702
- ^ Potočnik, Primož; Spiga, Pablo; Verret, Gabriel (2013)、「最大 1280 頂点の立方頂点推移グラフ」、Journal of Symbolic Computation、50 : 465–477、arXiv : 1201.5317、doi :10.1016/j.jsc.2012.09.002、MR 2996891。
- ^ Coxeter、Frucht & Powers (1981)、p. 10.