単純な3次グラフの表

頂点数が小さい場合の、 連結された 3 次正則 (立方)単純グラフがリストされます。

4、6、8、10、... 頂点に接続された単純立方グラフの数は 1、2、5、19、... です ( OEISのシーケンスA002851 )。 辺の接続性による分類は次のように行われます。1 接続および 2 接続のグラフは通常どおり定義されます。これにより、他のグラフは 3 接続クラスに残ります。これは、各 3 正則グラフは、任意の頂点に隣接するすべての辺を切断することで分割できるためです。 この定義を角運動量の結合の代数(以下を参照) に照らして精緻化するには、3 接続グラフの細分化が役立ちます。

• 非自明な3連結グラフとは、3つの辺で分割でき、各部分に少なくとも2つの頂点が残るグラフのことである。
• 巡回的に4連結 - 1連結でも2連結でも、非自明に3連結でもないものすべて

これは、下の表の 4 列目の数字 3 と 4 を宣言します。

表の別の列にあるグラフのボールと棒のモデルは、分子結合の画像のスタイルで頂点と辺を示しています。個々の図のコメントには、 内周、直径、ウィーナー指数、 エストラーダ指数、キルヒホッフ指数が含まれます。Aut はグラフの自己同型群の順序です。ハミルトン回路 (存在する場合) は、そのパスに沿って 1 から上に向かって頂点を列挙することによって示されます。(頂点の位置は、ユークリッド距離とグラフ理論距離の二乗差によって定義されるペア ポテンシャルを最小化することによって定義され、Molfileに配置され、 Jmolによってレンダリングされます。)

LCF表記法は、 Joshua Lederberg、Coxeter、Fruchtによる、ハミルトンの3 次グラフを表現する表記法です。

いずれかの頂点に隣接するサイクルに沿った 2 つの辺は書き込まれません。

グラフの頂点をvとし、 p頂点に沿ったハミルトン円を辺列v ₀ v ₁ , v ₁ v ₂ , ...,v _p−2 v _p−1 , v _p−1 v ₀で表す。頂点v _iで停止すると、距離d _iのところにv _iと弦で結ばれた唯一の頂点v _{j が}存在する。

${\displaystyle j=i+d_{i}\quad ({\bmod {\,}}p),\quad 2\leq d_{i}\leq p-2.}$

p個の整数のベクトル[d ₀ , d ₁ , ..., d _p−1 ]は、一意ではないものの、3次ハミルトングラフの適切な表現である。これには、2つの追加ルールが加わる。

1. d _i > p/2の場合はd _i − pに置き換えます。
2. d _iのシーケンスが周期的である場合は繰り返しを避け、指数表記に置き換えます。

パスの開始頂点は重要ではないため、表現内の数字は循環的に入れ替わる場合があります。グラフに異なるハミルトン回路が含まれている場合は、そのうちの 1 つを選択して表記法に対応できます。頂点の配置方法によっては、同じグラフでも異なる LCF 表記法が使用される場合があります。

多くの場合、反回文的表現は

${\displaystyle d_{p-1-i}=-d_{i}\quad ({\bmod {\,}}p),\quad i=0,1,\ldots p/2-1}$

が優先され（存在する場合）、冗長部分はセミコロンとダッシュ「; –」に置き換えられます。たとえば、LCF表記[5, −9, 7, −7, 9, −5] ^{4 は}、その段階で[5, −9, 7; –] ⁴に短縮されます。

グラフにハミルトン閉路がない場合、上記の LCF エントリは存在しませんが、これはまれです ( Tait の予想を参照)。この場合、3 番目の列で 0 から n−1 までラベル付けされた頂点のペア間の辺のリストが識別子として機能します。

2 n頂点上の 4 接続 (上記の意味で) の各単純立方グラフは、量子力学の3 n -j シンボルのクラスを定義します。大まかに言えば、各頂点は3-jm シンボルを表し、グラフは角運動量量子数jに符号を割り当てることによって有向グラフに変換され、頂点は 3-jm シンボル内の 3 つのj (3 つの辺のうち)の順序を表す利き手でラベル付けされ、グラフは頂点に割り当てられたこれらすべての数値の積の合計を表します。

これら（OEISの配列A175847）は、1（6-j）、1（9-j）、2（12-j ）、5（15-j ）、18（18-j ）、84（21-j ）、607（24-j ）、6100（27-j ）、78824（30-j ）、1195280（33-j ）、20297600（36-j ）、376940415（39-j ）などである。

これらが特定の頂点誘導二分木（1 つの辺を切断し、残りのグラフを 2 つの木に分割する切断を見つける）と同等である場合、これらは再結合係数の表現であり、Yutsis グラフ（OEISのシーケンスA111916）としても知られています。

• 3-jm シンボル
• 6-j シンボル

• Yutsis, AP ; Levinson, IB; Vanagas, VV; Sen, A. (1962). 角運動量理論の数学的装置。イスラエル科学翻訳プログラム。Bibcode : 1962mata.book .....Y.
• Massot, J.-N.; El-Baz, E.; Lafoucriere, J. (1967). 「角運動量の一般的なグラフ法」.現代物理学レビュー. 39 (2): 288– 305. Bibcode :1967RvMp...39..288M. doi :10.1103/RevModPhys.39.288.
• Bussemaker, FC; Cobeljic, S.; Cvetkovic, DM (1976) 「立方グラフのコンピュータ調査」(PDF)。
• Bussemaker, FC; Cobeljic, S.; Cvetkovic, DM; Seidel, JJ (1977). 「<=14 頂点の立方グラフ」. J. Combin. Theory Ser. B. 23 ( 2– 3 ): 234– 235. doi : 10.1016/0095-8956(77)90034-X .
• Frucht, R. (1977). 「三価ハミルトングラフの標準表現」.グラフ理論ジャーナル. 1 (1): 45– 60. doi :10.1002/jgt.3190010111. MR  0463029.
• Clark, L.; Entringer, R. (1983). 「最小の最大非ハミルトングラフ」. Per. Mathem. ハンガリー. 14 (1): 57– 68. doi :10.1007/BF02023582. MR  0697357. S2CID  122218690.
• Wormald, NC (1985). 「循環的に 4 連結された立方グラフの列挙」.グラフ理論ジャーナル. 9 (4): 563– 573. doi :10.1002/jgt.3190090418. MR  0890248.
• Bar-Shalom, A.; Klapisch, M. (1988). 「NJGRAF - グラフィカル解析による一般再結合係数の計算のための効率的なプログラム、NJSYM と互換性あり」。Comput . Phys. Commun . 50 (3): 375– 393. Bibcode :1988CoPhC..50..375B. doi :10.1016/0010-4655(88)90192-0.
• Brinkmann, G. (1996). 「立方グラフの高速生成」. Journal of Graph Theory . 23 (2): 139– 149. doi :10.1002/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.0.CO;2-U. MR  1408342.
• Fack, V.; Pitre, SN; Van der Jeugt, J. (1997). 「グラフィカル手法による一般再結合係数の計算」. Comput. Phys. Commun . 101 ( 1– 2): 155– 170. Bibcode :1997CoPhC.101..155F. doi :10.1016/S0010-4655(96)00170-1.
• Danos, M.; Fano, U. (1998). 「衝突生成物の角運動量のグラフィカル解析」. Physics Reports . 304 (4): 155– 227. Bibcode :1998PhR...304..155D. doi :10.1016/S0370-1573(98)00020-9.
• Meringer, M. (1999). 「正規グラフの高速生成とケージの構築」. Journal of Graph Theory . 30 (2): 137– 146. doi :10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G. MR  1665972.
• Van Dyck, D.; Brinkmann, G.; Fack, V.; McKay, BD (2005). 「Yutsis になるか、ならないか: 決定問題に対するアルゴリズム」. Comput. Phys. Commun . 173 ( 1– 2): 61– 70. Bibcode :2005CoPhC.173...61V. doi :10.1016/j.cpc.2005.07.008. MR  2179511.
• Van Dyck, D.; Fack, V. (2007). 「Yutsis グラフの縮小について」.離散数学. 307 ( 11– 12): 1506– 1515. doi : 10.1016/j.disc.2005.11.088 . MR  2311125.
• Aldred, REL; Van Dyck, D.; Brinkmann, G.; Fack, V.; McKay, BD (2009). 「高速認識を可能にする非 Yutsis グラフのグラフ構造特性」. Discrete Math . 157 (2): 377– 386. doi :10.1016/j.dam.2008.03.020. hdl : 1942/9184 . MR  2479811.
• Mathar, Richard J. (2011). 「12 頂点までの Wigner グラフ」. arXiv : 1109.2358 [math-ph].