The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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; text; internal format)



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.


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


Table of n, a(n) for n=2..19.

Dries Van Dyck, Veerle Fack, Yutsis project


Sequence in context: A320954 A322725 A245883 * A298361 A000109 A049338

Adjacent sequences:  A115337 A115338 A115339 * A115341 A115342 A115343




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



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 2 02:22 EDT 2020. Contains 335389 sequences. (Running on oeis4.)