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

Offset

2,3

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

Table of n, a(n) for n=2..19.

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

Formula

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

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 *)

Crossrefs

Cf. A000109, A007030.

Sequence in context: A322725 A339832 A245883 * A298361 A000109 A049338

Adjacent sequences: A115337 A115338 A115339 * A115341 A115342 A115343

Keyword

nice,nonn,more

Author

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

Status

approved