

A115340


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


0



1, 1, 2, 5, 14, 50, 233, 1248, 7593, 49536, 339483, 2404472, 17468202, 129459090, 975647292, 7458907217, 57744122366, 452028275567
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,3


COMMENTS

Yutsis graphs are connected cubic graphs which can be partitioned into two vertexinduced 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 vertexinduced forests among the connected cubic graphs (floor((6n2)/4) for a graph on 2n nodes). Whitney showed in 1931 that proving the 4color theorem for a planar Yutsis graph implies the theorem for all planar graphs.


REFERENCES

F. Jaeger, On vertex inducedforests in cubic graphs, Proceedings 5th Southeastern Conference, Congressus Numerantium (1974) 501512
L. H. Kauffman, Map Coloring and the Vector Cross Product, Journal of Combinatorial Theory, Series B, 48 (1990) 145154
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) 6170


LINKS

Table of n, a(n) for n=2..19.
Dries Van Dyck, Veerle Fack, Yutsis project


CROSSREFS

Sequence in context: A320954 A322725 A245883 * A298361 A000109 A049338
Adjacent sequences: A115337 A115338 A115339 * A115341 A115342 A115343


KEYWORD

nice,nonn


AUTHOR

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


STATUS

approved



