|
Search: id:A115340
|
|
|
| A115340 |
|
Number of dual hamiltonian cubic polyhedra or planar 3-connected Yutsis graphs on 2n nodes. |
|
+0
1
|
|
| 1, 1, 2, 5, 14, 50, 233, 1248, 7593, 49536, 339483, 2404472, 17468202, 129459090, 975647292, 7458907217, 57744122366, 452028275567
(list; graph; listen)
|
|
|
OFFSET
|
2,3
|
|
|
COMMENT
|
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 this_sequence A000109 A049338 A115275
Adjacent sequences: A115337 A115338 A115339 this_sequence A115341 A115342 A115343
|
|
KEYWORD
|
nice,nonn
|
|
AUTHOR
|
Dries Van Dyck (VanDyck.Dries(AT)Gmail.com), Mar 06 2006
|
|
|
Search completed in 0.002 seconds
|
