A115340 Number of dual Hamiltonian cubic polyhedra or planar 3-connected Yutsis graphs on 2n nodes.

1, 1, 2, 5, 14, 50, 233, 1248, 7593, 49536, 339483, 2404472, 17468202, 129459090, 975647292, 7458907217, 57744122366, 452028275567, 3573870490382

Offset: 2

Author

Dries Van Dyck (VanDyck.Dries(AT)gmail.com), Mar 06 2006

Keywords

• nice
• nonn
• more

Comments

Also, a(n) is the number of Hamiltonian planar triangulations with n+2 vertices. - Brendan McKay, Feb 20 2021

Yutsis graphs are connected cubic graphs which can be partitioned into two vertex-induced trees, which are necessarily of the same size. The cut separating both trees contains n+2 edges for a graph on 2n nodes, forming a Hamiltonian cycle in the planar dual if the graph is planar. These graphs are maximal in the number of nodes of the largest vertex-induced forests among the connected cubic graphs (floor((6n-2)/4) for a graph on 2n nodes). Whitney showed in 1931 that proving the 4-color theorem for a planar Yutsis graph implies the theorem for all planar graphs.

References

• F. Jaeger, On vertex induced-forests in cubic graphs, Proceedings 5th Southeastern Conference, Congressus Numerantium (1974) 501-512.

Links

• L. H. Kauffman, Map Coloring and the Vector Cross Product, Journal of Combinatorial Theory, Series B, 48 (1990) 145-154.
• D. Van Dyck, G. Brinkmann, V. Fack and B. D. McKay, To be or not to be Yutsis: algorithms for the decision problem, Computer Physics Communications 173 (2005) 61-70.
• Dries Van Dyck and Veerle Fack, Yutsis project

Crossrefs

Cf. A000109, A007030.

Programs

Mathematica

A000109 = Cases[Import["https://oeis.org/A000109/b000109.txt", "Table"], {, }][[All, 2]];
A007030 = Cases[Import["https://oeis.org/A007030/b007030.txt", "Table"], {, }][[All, 2]];
a[n_] := A000109[[n]] - A007030[[n+2]];
Table[a[n], {n, 2, 19}] (* Jean-François Alcover, Jul 20 2022 *)

Formula

a(n) = A000109(n+2) - A007030(n+2). - William P. Orrick, Feb 20 2021

Extensions

a(20) from Van Dyck et al. added by Andrey Zabolotskiy, Sep 10 2024