Tabla de grafos cúbicos simples

Se enumeran los gráficos simples 3-regulares ( cúbicos ) conectados para números de vértices pequeños.

El número de grafos cúbicos simples conexos en 4, 6, 8, 10, ... vértices es 1, 2, 5, 19, ... (secuencia A002851 en la OEIS ). Se realiza una clasificación según la conectividad de las aristas de la siguiente manera: los grafos 1-conexos y 2-conexos se definen como de costumbre. Esto deja a los otros grafos en la clase 3-conexos porque cada grafo 3-regular se puede dividir cortando todas las aristas adyacentes a cualquiera de los vértices. Para refinar esta definición a la luz del álgebra de acoplamiento de momentos angulares (ver más abajo), es útil una subdivisión de los grafos 3-conexos. Llamaremos

• No trivialmente 3-conectados aquellos que pueden dividirse por 3 cortes de arista en subgrafos con al menos dos vértices restantes en cada parte
• Cíclicamente 4-conectados: todos aquellos que no están 1-conectados, no están 2-conectados y no están 3-conectados de manera no trivial.

Esto declara los números 3 y 4 en la cuarta columna de las tablas siguientes.

Los modelos de bolas y palos de los grafos en otra columna de la tabla muestran los vértices y las aristas en el estilo de imágenes de enlaces moleculares. Los comentarios sobre las imágenes individuales contienen circunferencia , diámetro , índice de Wiener , índice de Estrada e índice de Kirchhoff . Aut es el orden del grupo de automorfismo del grafo. Un circuito hamiltoniano (cuando está presente) se indica enumerando los vértices a lo largo de esa trayectoria desde 1 hacia arriba. (Las posiciones de los vértices se han definido minimizando un potencial de par definido por la diferencia al cuadrado de la distancia euclidiana y la teórica del grafo, colocada en un Molfile y luego renderizada por Jmol ).

La notación LCF es una notación de Joshua Lederberg , Coxeter y Frucht , para la representación de gráficos cúbicos que son hamiltonianos .

Los dos bordes a lo largo del ciclo adyacentes a cualquiera de los vértices no se escriben.

Sean v los vértices del grafo y describamos el círculo hamiltoniano a lo largo de los p vértices mediante la secuencia de aristas v ₀ v ₁ , v ₁ v ₂ , ...,v _p−2 v _p−1 , v _p−1 v ₀ . Al detenerse en un vértice v _i , hay un único vértice v _j a una distancia d _i unido por una cuerda con v _i ,

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

El vector [d ₀ , d ₁ , ..., d _p−1 ] de los p enteros es una representación adecuada, aunque no única, del grafo hamiltoniano cúbico. Esto se complementa con dos reglas adicionales:

1. Si a d _i > p/2 , reemplácelo por d _i − p ;
2. evitar la repetición de una secuencia de d _i si estas son periódicas y reemplazarlas por una notación exponencial.

Dado que el vértice inicial de la trayectoria no tiene importancia, los números en la representación pueden permutarse cíclicamente. Si un gráfico contiene diferentes circuitos hamiltonianos, se puede seleccionar uno de ellos para adaptar la notación. El mismo gráfico puede tener diferentes notaciones de LCF, dependiendo de cómo se dispongan los vértices.

A menudo las representaciones antipalindrómicas con

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

se prefieren (si existen), y la parte redundante se reemplaza entonces por un punto y coma y un guión "; –". La notación LCF [5, −9, 7, −7, 9, −5] ⁴ , por ejemplo, y en esa etapa se condensaría a [5, −9, 7; –] ⁴ .

The LCF entries are absent above if the graph has no Hamiltonian cycle, which is rare (see Tait's conjecture). In this case a list of edges between pairs of vertices labeled 0 to n−1 in the third column serves as an identifier.

Each 4-connected (in the above sense) simple cubic graph on 2n vertices defines a class of quantum mechanical 3n-j symbols. Roughly speaking, each vertex represents a 3-jm symbol, the graph is converted to a digraph by assigning signs to the angular momentum quantum numbers j, the vertices are labelled with a handedness representing the order of the three j (of the three edges) in the 3-jm symbol, and the graph represents a sum over the product of all these numbers assigned to the vertices.

There are 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) etc. of these (sequence A175847 in the OEIS).

If they are equivalent to certain vertex-induced binary trees (cutting one edge and finding a cut that splits the remaining graph into two trees), they are representations of recoupling coefficients, and are then also known as Yutsis graphs (sequence A111916 in the OEIS).

• 3-jm symbol
• 6-j symbol

• Yutsis, A. P.; Levinson, I. B.; Vanagas, V. V.; Sen, A. (1962). Mathematical Apparatus of the theory of angular momentum. Israel program for scientific translations. Bibcode:1962mata.book.....Y.
• Massot, J.-N.; El-Baz, E.; Lafoucriere, J. (1967). "A general graphical method for angular momentum". Reviews of Modern Physics. 39 (2): 288–305. Bibcode:1967RvMp...39..288M. doi:10.1103/RevModPhys.39.288.
• Bussemaker, F. C.; Cobeljic, S.; Cvetkovic, D. M. (1976). "Computer investigations of cubic graphs" (PDF).
• Bussemaker, F. C.; Cobeljic, S.; Cvetkovic, D. M.; Seidel, J. J. (1977). "Cubic graphs on <=14 vertices". J. Combin. Theory Ser. B. 23 (2–3): 234–235. doi:10.1016/0095-8956(77)90034-X.
• Frucht, R. (1977). "A canonical representation of trivalent Hamiltonian graphs". Journal of Graph Theory. 1 (1): 45–60. doi:10.1002/jgt.3190010111. MR 0463029.
• Clark, L.; Entringer, R. (1983). "Smallest maximally non-Hamiltonian graphs". Per. Mathem. Hungar. 14 (1): 57–68. doi:10.1007/BF02023582. MR 0697357. S2CID 122218690.
• Wormald, N. C. (1985). "Enumeration of cyclically 4-connected cubic graphs". Journal of Graph Theory. 9 (4): 563–573. doi:10.1002/jgt.3190090418. MR 0890248.
• Bar-Shalom, A.; Klapisch, M. (1988). "NJGRAF - an efficient program for calculation of general recoupling coefficients by graphical analysis, compatible with NJSYM". Comput. Phys. Commun. 50 (3): 375–393. Bibcode:1988CoPhC..50..375B. doi:10.1016/0010-4655(88)90192-0.
• Brinkmann, G. (1996). "Fast generation of cubic graphs". 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, S. N.; Van der Jeugt, J. (1997). "Calculation of general recoupling coefficients using graphical methods". 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). "Graphical analysis of angular momentum for collision products". Physics Reports. 304 (4): 155–227. Bibcode:1998PhR...304..155D. doi:10.1016/S0370-1573(98)00020-9.
• Meringer, M. (1999). "Fast generation of regular graphs and construction of cages". 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, B. D. (2005). "To be or not to be Yutsis: Algorithms for the decision problem". 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). "On the reduction of Yutsis graphs". Discrete Math. 307 (11–12): 1506–1515. doi:10.1016/j.disc.2005.11.088. MR 2311125.
• Aldred, R. E. L.; Van Dyck, D.; Brinkmann, G.; Fack, V.; McKay, B. D. (2009). "Graph structural properties of non-Yutsis graphs allowing fast recognition". Discrete Math. 157 (2): 377–386. doi:10.1016/j.dam.2008.03.020. hdl:1942/9184. MR 2479811.
• Mathar, Richard J. (2011). "Gráficos de Wigner de hasta 12 vértices". arXiv : 1109.2358 [math-ph].