A007030 -id:A007030 - cp's OEIS frontend

A007031 Non-Hamiltonian 1-tough simplicial polyhedra with n nodes.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 72, 847, 9801

Offset: 1

A graph is 1-tough if there is no set of k vertices whose deletion splits the graph into more than k components. - Hugo Pfoertner citing William P. Orrick in A342971, Aug 04 2021

M. B. Dillencourt, Polyhedra of small orders and their Hamiltonian properties. Tech. Rep. 92-91, Info. and Comp. Sci. Dept., Univ. Calif. Irvine, 1992.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. B. Dillencourt, Polyhedra of small orders and their Hamiltonian properties, J. Comb. Theory, Ser. B, 66 (1996) 87-122.

Cf. A007030.

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

Original entry on oeis.org

1, 1, 2, 5, 14, 50, 233, 1248, 7593, 49536, 339483, 2404472, 17468202, 129459090, 975647292, 7458907217, 57744122366, 452028275567, 3573870490382

Offset: 2

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

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.

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.
Dries Van Dyck and Veerle Fack, Yutsis project

Cf. A000109, A007030.

A000109 = Cases[Import["https://oeis.org/A000109/b000109.txt", "Table"], {, }][[All, 2]];
A007030 = Cases[Import["https://oeis.org/A007030/b007030.txt", "Table"], {, }][[All, 2]];
a[n_] := A000109[[n]] - A007030[[n+2]];
Table[a[n], {n, 2, 19}] (* Jean-François Alcover, Jul 20 2022 *)

a(n) = A000109(n+2) - A007030(n+2). - William P. Orrick, Feb 20 2021

a(20) from Van Dyck et al. added by Andrey Zabolotskiy, Sep 10 2024

A342971 Non-1-tough simplicial polyhedra with n nodes.

Original entry on oeis.org

1, 2, 29, 233, 2297, 21192, 195862

Offset: 11

William P. Orrick, Apr 01 2021

A graph is 1-tough if there is no set of k vertices whose deletion splits the graph into more than k components.

If a graph is not 1-tough then it is not Hamiltonian.

Cf. A000109, A115340, A007030, A007031.

a(n) = A007030(n) - A007031(n).

cp's OEIS Frontend

A007031 Non-Hamiltonian 1-tough simplicial polyhedra with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A342971 Non-1-tough simplicial polyhedra with n nodes.

Views

Author

Keywords

Comments

Crossrefs

Formula