[seqfan] Counting 4-connected simple cubic graphs

Richard Mathar mathar at strw.leidenuniv.nl
Wed Sep 22 13:26:24 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

Some background is in the unstable http://www.strw.leidenuniv.nl/~mathar/public/mathar20100916.pdf .
Richard Mathar

More information about the SeqFan mailing list