[seqfan] Re: Seqfan Digest, Vol 24, Issue 12

Brendan McKay bdm at cs.anu.edu.au
Thu Sep 23 11:21:56 CEST 2010

> Can someone recount or add more terms to this one:
> %I A000001
> %S A000001 1,1,2,5,18,84,607
> %N A000001 Number of 4-connected simple cubic graphs on 2n vertices.
> %C A000001 The (edge-)connected simple cubic graphs counted in A002851 can be classified as 1-connected
> %C A000001 (containing bridges), 2-connected, non-trivially 3-connected (not allowing the cut through
> %C A000001 all edges adjacent to a single vertex), and 4-connected. Each of the non-isomorphic 4-connected graphs
> %C A000001 defines a 3n-j symbol of the vector coupling coefficients in the quantum mechanics of SO(3),
> %C A000001 one 6j symbol, one 9j symbol, two 12j symbols, five 15j symbols etc. The Yutsis graphs are
> %C A000001 a subset of these 4-connected graphs, if they admit a representation as vertex-induced binary trees.
> %D A000001 A. P. Yutsis, I. B. Levinson, V. V. Vanagas, A. Sen, Mathematical apparatus of the theory of angular momentum (1962)
> %H A000001 J.-N. Massot, E. El-Baz, J. Lafoucriere, <a href="http://dx.doi.org/10.1103/RevModPhys.39.288">A general graphical method for angular momentum</a>, Rev. Mod. Phys. 39 (2) (1967) 288-305
> %H A000001 G. Brinkmann, <a href="http://dx.doi.org/10.1002/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.0.CO;2-U"></a>, J. Graph Theory 23 (2) (1995) 139-149
> %H A000001 M. Meringer, <a href="http://dx.doi.org/10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G">Fast generation of regular graphs and construction of cages</a>, J. Graph Theory 30 (2) (1999) 137-146
> %H A000001 D. van Dyck, G. Brinkman, V. Fack, D. B. McKay, <a href="http://dx.doi.org/10.1016/j.cpc.2005.07.008">To be or not to be Yutsis: algorithms for the decision problem</a>, Comp. Phys. Comm. 173 (1-2) (2005) 61-70
> %e A000001 On 4 vertices we count a(2)=1, the tetrahedron.
> %e A000001 On 6 vertices we count the wheel graph as a(3)=1, but not the 3-connected utility graph.
> %Y A000001 Cf. A111916
> %K A000001 nonn,new
> %O A000001 2,3
> %A A000001 Missing term inserted by R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Sep 22 2010
Usually these are called "cyclically 4-connected". It is bad
terminology to call them "4-connected".

Gunnar Brinkmann at Ghent has a program for making them.  His student
Jan Goedgebeur sent these counts up to 26 vertices:


The labelled graphs in this class are counted by A007101.


More information about the SeqFan mailing list