4-connected projective planar graphs are Hamiltonian (Q1333330)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: 4-connected projective planar graphs are Hamiltonian |
scientific article; zbMATH DE number 638651
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | 4-connected projective planar graphs are Hamiltonian |
scientific article; zbMATH DE number 638651 |
Statements
4-connected projective planar graphs are Hamiltonian (English)
0 references
1 December 1994
0 references
We prove the result stated in the title (conjectured by Grünbaum) and a conjecture of Plummer that every graph which can be obtained from a 4- connected planar graph by deleting two vertices is Hamiltonian. The proofs are constructive and give rise to polynomial-time algorithms.
0 references
Grünbaum conjecture
0 references
Plummer conjecture
0 references
projective-planar graphs
0 references
Hamiltonian
0 references
polynomial-time algorithms
0 references
0.99300444
0 references
0.99300444
0 references
0.9340022
0 references
0.92797214
0 references
0.9233688
0 references
0 references
0.90709895
0 references
0.9002485
0 references
