|
%I #23 Jul 20 2022 07:43:05
%S 1,1,2,5,14,50,233,1248,7593,49536,339483,2404472,17468202,129459090,
%T 975647292,7458907217,57744122366,452028275567
%N Number of dual Hamiltonian cubic polyhedra or planar 3-connected Yutsis graphs on 2n nodes.
%C Also, a(n) is the number of Hamiltonian planar triangulations with n+2 vertices. - _Brendan McKay_, Feb 20 2021
%C 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.
%D F. Jaeger, On vertex induced-forests in cubic graphs, Proceedings 5th Southeastern Conference, Congressus Numerantium (1974) 501-512.
%H L. H. Kauffman, <a href="https://doi.org/10.1016/0095-8956(90)90114-F">Map Coloring and the Vector Cross Product</a>, Journal of Combinatorial Theory, Series B, 48 (1990) 145-154.
%H D. Van Dyck, G. Brinkmann, V. Fack and B. D. McKay, <a href="https://doi.org/10.1016/j.cpc.2005.07.008">To be or not to be Yutsis: algorithms for the decision problem</a>, Computer Physics Communications 173 (2005) 61-70.
%H Dries Van Dyck and Veerle Fack, <a href="http://caagt.ugent.be/yutsis/">Yutsis project</a>
%F a(n) = A000109(n+2) - A007030(n+2). - _William P. Orrick_, Feb 20 2021
%t A000109 = Cases[Import["https://oeis.org/A000109/b000109.txt", "Table"], {_, _}][[All, 2]];
%t A007030 = Cases[Import["https://oeis.org/A007030/b007030.txt", "Table"], {_, _}][[All, 2]];
%t a[n_] := A000109[[n]] - A007030[[n+2]];
%t Table[a[n], {n, 2, 19}] (* _Jean-François Alcover_, Jul 20 2022 *)
%Y Cf. A000109, A007030.
%K nice,nonn,more
%O 2,3
%A Dries Van Dyck (VanDyck.Dries(AT)gmail.com), Mar 06 2006
|
