4-connected projective planar graphs are Hamiltonian (Q1333330): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1006/jctb.1994.1058 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1988180925 / rank | |||
Normal rank | |||
Latest revision as of 22:36, 19 March 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
