4-connected projective planar graphs are Hamiltonian (Q1333330): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 13:59, 31 January 2024
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