4-connected projective planar graphs are Hamiltonian
From MaRDI portal
Publication:1333330
DOI10.1006/jctb.1994.1058zbMath0802.05051MaRDI QIDQ1333330
Publication date: 1 December 1994
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1994.1058
Hamiltonian; polynomial-time algorithms; Grünbaum conjecture; Plummer conjecture; projective-planar graphs
68R10: Graph theory (including graph drawing) in computer science
05C10: Planar graphs; geometric and topological aspects of graph theory
05C85: Graph algorithms (graph-theoretic aspects)
05C45: Eulerian and Hamiltonian graphs
Related Items
On 2-connected spanning subgraphs with low maximum degree, Spanning Eulerian subgraphs of bounded degree in triangulations, Graph-theoretical conditions for inscribability and Delaunay realizability, Tutte cycles in circuit graphs, Vertices of small degree in uniquely Hamiltonian graphs, On Hamiltonian cycles in 4- and 5-connected plane triangulations, Finding Hamiltonian cycles in Delaunay triangulations is NP-complete, Disjoint paths, planarizing cycles, and spanning walks