4-connected projective planar graphs are Hamiltonian (Q1333330): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
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 | |||
links / mardi / name | links / mardi / name | ||
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