4-connected projective planar graphs are Hamiltonian
From MaRDI portal
Publication:1333330
DOI10.1006/jctb.1994.1058zbMath0802.05051OpenAlexW1988180925MaRDI 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
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)
Related Items (67)
Spanning Eulerian subgraphs of bounded degree in triangulations ⋮ Cycles in 4-connected planar graphs ⋮ Counting Hamiltonian cycles in planar triangulations ⋮ Unnamed Item ⋮ Every 5-connected planar triangulation is 4-ordered Hamiltonian ⋮ Graph-theoretical conditions for inscribability and Delaunay realizability ⋮ 5-Connected Toroidal Graphs are Hamiltonian-Connected ⋮ Chords of longest circuits in locally planar graphs ⋮ The circumference of a graph with no \(K_{3,t}\)-minor ⋮ Hamiltonicity and colorings of arrangement graphs ⋮ Every 4-Connected Graph with Crossing Number 2 is Hamiltonian ⋮ Finding Hamiltonian cycles in Delaunay triangulations is NP-complete ⋮ 2-connected spanning subgraphs with low maximum degree in locally planar graphs ⋮ Computing Tutte Paths ⋮ Tutte cycles in circuit graphs ⋮ The 2-extendability of graphs on the projective plane, the torus and the Klein bottle ⋮ Hamiltonian Cycles in 4-Connected Planar and Projective Planar Triangulations with Few 4-Separators ⋮ On the circumference of 3-connected cubic triangle-free plane graphs ⋮ On 2-connected spanning subgraphs with low maximum degree ⋮ The circumference of a graph with no \(K_{3,t}\)-minor. II ⋮ Find subtrees of specified weight and cycles of specified length in linear time ⋮ \([a,b\)-factors of graphs on surfaces] ⋮ On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs ⋮ Relationship among triangulations, quadrangulations and optimal 1-planar graphs ⋮ Rooted minors and locally spanning subgraphs ⋮ K2‐Hamiltonian graphs: II ⋮ Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey ⋮ Subgraphs of graphs on surfaces with high representativity ⋮ Recent advances on the Hamiltonian problem: survey III ⋮ Cycle traversability for claw-free graphs and polyhedral maps ⋮ Spanning closed walks and TSP in 3-connected planar graphs ⋮ Structural properties for certain classes of infinite planar graphs ⋮ Polyhedra with few 3-cuts are Hamiltonian ⋮ Non-Hamiltonian triangulations with distant separating triangles ⋮ The matching extendability of optimal 1-planar graphs ⋮ Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs ⋮ Hamilton paths in toroidal graphs ⋮ Unnamed Item ⋮ The 2-extendability of 5-connected graphs on the Klein bottle ⋮ What is on his mind? ⋮ A note on traversing specified vertices in graphs embedded with large representativity ⋮ Unnamed Item ⋮ Hamiltonian properties of polyhedra with few 3-cuts. A survey ⋮ 2- and 3-factors of graphs on surfaces ⋮ 2-edge-Hamiltonian-connectedness of 4-connected plane graphs ⋮ Cycles in 5-connected triangulations ⋮ Criticality of counterexamples to toroidal edge-Hamiltonicity ⋮ Hamilton circles in infinite planar graphs ⋮ Long cycles in 4-connected planar graphs ⋮ Maximum bipartite subgraphs of cubic triangle-free planar graphs ⋮ Types of triangle in Hamiltonian triangulations and an application to domination and k-walks ⋮ Cycle spectra of contraction-critically 4-connected planar graphs ⋮ Vertices of small degree in uniquely Hamiltonian graphs ⋮ Number of Hamiltonian Cycles in Planar Triangulations ⋮ Book Embedding of Graphs on the Projective Plane ⋮ Non-Hamiltonian 1-tough triangulations with disjoint separating triangles ⋮ Hamiltonian cycles in bipartite quadrangulations on the torus ⋮ On Hamiltonian cycles in 4- and 5-connected plane triangulations ⋮ Disjoint paths, planarizing cycles, and spanning walks ⋮ $K_2$-Hamiltonian Graphs: I ⋮ Long cycles in graphs on a fixed surface ⋮ Diagonal flips in Hamiltonian triangulations on the projective plane ⋮ Tutte paths and long cycles in circuit graphs ⋮ Unnamed Item ⋮ 4-connected projective-planar graphs are Hamiltonian-connected ⋮ Distribution of subtree sums ⋮ Equivalence of Jackson's and Thomassen's conjectures
This page was built for publication: 4-connected projective planar graphs are Hamiltonian
