|
| |
|
|
A115340
|
|
Number of dual hamiltonian cubic polyhedra or planar 3-connected 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; internal format)
|
|
|
|
OFFSET
| 2,3
|
|
|
COMMENTS
| Yutsis graphs are connected cubic graphs which can be partitioned into two vertex-induced trees, which are necessarily of the same size. The cut seperating 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
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
|
|
|
LINKS
| Dries Van Dyck, Veerle Fack, Yutsis project
|
|
|
CROSSREFS
| Sequence in context: A006390 A100597 A022562 * A000109 A049338 A115275
Adjacent sequences: A115337 A115338 A115339 * A115341 A115342 A115343
|
|
|
KEYWORD
| nice,nonn
|
|
|
AUTHOR
| Dries Van Dyck (VanDyck.Dries(AT)Gmail.com), Mar 06 2006
|
| |
|
|
