No label defined (Q3313897)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3843793
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3843793

      Statements

      0 references
      1984
      0 references
      simple 3-polytope
      0 references
      Hamiltonian circuit
      0 references
      forbidden subgraphs
      0 references
      [For the entire collection see Zbl 0521.00010.] The author shows that each simple 3-polytope with at most 30 vertices is Hamiltonian. The proof works by generating a certain subfamily of these polytopes and checking its members for Hamiltonian circuits by computer. It is based on two theorems about forbidden subgraphs in an eventual counterexample with minimum number of vertices. The first one is obvious, the second one was originally proved (in a more general form) by \textit{J. W. Butler} [Recent Adv. Graph Theory, Proc. Symp. Prague 1974, 135-151 (1975; Zbl 0332.05113)]. \textit{H. Okamura} has shown that all simple 3- polytopes with up to 32 vertices are Hamiltonian [J. Graph Theory 6, 185- 196 (1982; Zbl 0493.05043)]. His proof does not use a computer.
      0 references

      Identifiers