Loading article…
数学のグラフ理論の分野において、グラフ Gが対称（または弧推移）であるとは、 Gの任意の2つの隣接する頂点のペア u 1 — v 1とu 2 — v 2に対して、自己同型が存在することを意味する。
そのような
- および[1]
言い換えれば、グラフの自己同型群が隣接する頂点の順序付きペア（つまり、方向を持つと見なされる辺）に対して推移的に作用する場合、そのグラフは対称的である。 [2]このようなグラフは、 1弧推移的[2]またはフラグ推移的[3]とも呼ばれる。
定義により（u 1とu 2を無視）、孤立した頂点のない対称グラフは、頂点推移的でもある必要があります。[1]上記の定義は、1つの辺を別の辺にマッピングするため、対称グラフは辺推移的でもある必要があります。ただし、a—b はc—dにマッピングされる可能性がありますが、d—cにはマッピングされないため、辺推移グラフは対称である必要はありません。スターグラフは、頂点推移的でも対称的でもないが、辺推移的である単純な例です。さらに例として、半対称グラフは辺推移的で正則ですが、頂点推移的ではありません。
| 自己同型によって定義されるグラフ族 | ||||
|---|---|---|---|---|
| 距離推移 | → | 距離-通常 | ← | 強く規則的な |
| ↓ | ||||
| 対称的（弧推移的） | ← | t推移的、t ≥ 2 | 歪対称 | |
| ↓ | ||||
| （接続されている場合） 頂点および辺が推移的 |
→ | エッジ推移と正規 | → | エッジ推移 |
| ↓ | ↓ | ↓ | ||
| 頂点推移 | → | 通常 | → | （二部構成の場合） 双正則 |
| ↑ | ||||
| ケーリーグラフ | ← | ゼロ対称 | 非対称 | |
したがって、連結された対称グラフはすべて、頂点推移的かつ辺推移的である必要があり、逆は奇数次数のグラフに対しても当てはまります。[3] ただし、偶数次数の場合、頂点推移的かつ辺推移的であるが対称ではない連結グラフが存在します。[4]このようなグラフは半推移的 と呼ばれます。[5]連結された半推移グラフの最小値は、次数4で頂点が27個のホルトのグラフです。 [1] [6]紛らわしいことに、一部の著者は「対称グラフ」という用語を、弧推移グラフではなく、頂点推移的かつ辺推移的なグラフの意味で使用しています。このような定義には、上記の定義では除外されている半推移グラフが含まれます。
距離推移グラフとは、隣接する頂点のペア（つまり、距離が 1 離れた頂点）を考慮する代わりに、定義がそれぞれ同じ距離にある 2 つの頂点のペアをカバーするグラフです。このようなグラフは、定義により自動的に対称になります。[1]
t弧はt + 1 個の頂点の列として定義され、その列内の連続する 2 つの頂点は隣接しており、繰り返される頂点は 2 ステップ以上離れている。t推移グラフは、自己同型群がt弧に対して推移的に作用するが、( t + 1 ) 弧に対しては作用しないグラフである。 1 弧は単なる辺であるため、次数 3 以上の対称グラフはすべて、何らかのtに対してt推移的である必要があり、 tの値を使用して対称グラフをさらに分類することができる。たとえば、立方体は2 推移的である。 [1]
慣例上、「対称グラフ」という用語は「非対称グラフ」という用語の補足用語ではないことに注意してください。後者は、非自明な対称性がまったくないグラフを指します。
例
任意の数の頂点に対する対称グラフの 2 つの基本的なファミリは、サイクル グラフ(次数 2) と完全グラフです。さらに対称グラフは、正多面体と準正多面体の頂点と辺によって形成されます。立方体、正八面体、二十面体、十二面体、立方八面体、二十二十十二面体です。立方体を n 次元に拡張すると、ハイパーキューブ グラフ (頂点数が 2 nで次数が n) が得られます。同様に、八面体を n 次元に拡張すると、交差多面体のグラフが得られます。このグラフ ファミリ (頂点数が 2n で次数が 2n-2) は、カクテル パーティー グラフと呼ばれることもあります。これは、完全マッチングを行う辺のセットが削除された完全グラフです。頂点数が偶数 2n である対称グラフの追加の族には、均等に分割された完全な二部グラフK n,nと、頂点数が 2n のクラウン グラフがあります。他の多くの対称グラフは巡回グラフとして分類できます(ただし、すべてではありません)。
ラドー グラフは、頂点が無限にあり、次数が無限である対称グラフの例です。
立方対称グラフ
対称性条件と、グラフが立方体でなければならない（つまり、すべての頂点の次数が 3 である）という制約を組み合わせると、非常に強い条件が得られ、そのようなグラフはリストに載せられるほどまれである。それらはすべて頂点の数が偶数である。フォスター センサスとその拡張は、そのようなリストを提供している。[7]フォスター センサスは、ロナルド M. フォスターがベル研究所に勤務していた1930 年代に開始され、[8] 1988 年（フォスターが 92 歳[1]のとき）に、当時の最新のフォスター センサス（512 頂点までの立方体対称グラフをすべてリストしたもの）が書籍として出版された。[9] リストの最初の 13 項目は、最大 30 頂点の立方体対称グラフである[10] [11]（これらのうち 10 項目は距離推移的でもある。例外は示されているとおりである）。
他によく知られている 3 次対称グラフには、ディク グラフ、フォスター グラフ、ビッグス スミス グラフがあります。上記の 10 個の距離推移グラフは、フォスター グラフとビッグス スミス グラフとともに、唯一の 3 次距離推移グラフです。
プロパティ
対称グラフの頂点連結性は常に次数dに等しい。[ 3 ]対照的に、一般に頂点推移グラフの場合、頂点連結性は2( d + 1)/3以下に制限される。[2]
次数 3 以上の t 推移グラフは、内周が少なくとも 2( t – 1) である。しかし、t ≥ 8 の場合、次数 3 以上の 有限t推移グラフ は存在しない。 次数がちょうど 3 の場合 (立方対称グラフ)、 t ≥ 6 の場合、有限 t 推移グラフは存在しない。
参照
参考文献
- ^ abcdef ビッグス、ノーマン（1993）。代数的グラフ理論（第2版）。ケンブリッジ：ケンブリッジ大学出版局。pp. 118–140。ISBN 0-521-45897-8。
- ^ abc Godsil, Chris ; Royle, Gordon (2001).代数的グラフ理論. ニューヨーク: Springer. p. 59. ISBN 0-387-95220-9。
- ^ abc Babai, L (1996). 「自己同型群、同型性、再構築」(PDF)。 Graham, R; Grötschel, M ; Lovász, L (編)。Handbook of Combinatorics。 Elsevier。
- ^ Bouwer, Z. (1970). 「頂点と辺は推移的だが、1-推移的ではないグラフ」.カナダ数学ブル. 13 : 231–237. doi : 10.4153/CMB-1970-047-8 .
- ^ Gross, JL & Yellen, J. (2004).グラフ理論ハンドブック. CRC Press. p. 491. ISBN 1-58488-090-2。
- ^ Holt, Derek F. (1981). 「辺は推移的だが弧は推移的ではないグラフ」. Journal of Graph Theory . 5 (2): 201–204. doi :10.1002/jgt.3190050210.。
- ^ マーストン・コンダー、「768 頂点までの三価対称グラフ」、 J. Combin. Math. Combin. Comput、vol. 20、pp. 41–63
- ^ フォスター、RM「電気ネットワークの幾何学的回路」アメリカ電気学会誌 51、309-317、1932年。
- ^ 「フォスター国勢調査: RM フォスターの連結対称三価グラフ国勢調査」、ロナルド M. フォスター、IZ バウワー、WW チェルノフ、B. モンソン、Z. スター (1988) ISBN 0-919611-19-2
- ^ ビッグス、148ページ
- ^ ab Weisstein, Eric W.、「Cubic Symmetric Graph」、Wolfram MathWorld より。
外部リンク
- 立方対称グラフ (The Foster Census)。頂点数が 768 までのすべての立方対称グラフと、頂点数が 1000 までのいくつかの立方グラフのデータ ファイル。Gordon Royle、2001 年 2 月に更新、2009 年 4 月 18 日に取得。
- 最大 10000 頂点の三価 (立方) 対称グラフ。Marston Conder、2011 年。