4-connected projective planar graphs are Hamiltonian (Q1333330)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | 4-connected projective planar graphs are Hamiltonian |
scientific article |
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
