|
|
A115340
|
|
Number of dual Hamiltonian cubic polyhedra or planar 3-connected Yutsis graphs on 2n nodes.
|
|
2
|
|
|
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
|
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
|
|
|
FORMULA
|
|
|
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]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nice,nonn,more
|
|
AUTHOR
|
Dries Van Dyck (VanDyck.Dries(AT)gmail.com), Mar 06 2006
|
|
STATUS
|
approved
|
|
|
|