Updating the hamiltonian problem—A survey

DOI10.1002/jgt.3190150204zbMath0746.05039OpenAlexW1975951388MaRDI QIDQ3978362

Publication date: 25 June 1992

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190150204

zbMATH Keywords

distance random graphs Hamiltonian paths toughness neighborhood intersection

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items

The Hamiltonian properties in \(K_{1,r}\)-free split graphs ⋮ Hamiltonicity in claw-free graphs through induced bulls ⋮ Chvátal–Erdős Theorem: Old Theorem with New Aspects ⋮ An efficient condition for a graph to be Hamiltonian ⋮ Claw-free graphs---a survey ⋮ Partitioning a Graph into Highly Connected Subgraphs ⋮ Hamiltonian properties on the class of hypercube-like networks ⋮ Hamiltonicity of the cross product of two Hamiltonian graphs ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Bipartite independent number and Hamilton-biconnectedness of bipartite graphs ⋮ Unnamed Item ⋮ A new Chvátal type condition for pancyclicity ⋮ Connected graph \(G\) with \(\sigma_2(G) \geq \frac{2}{3} n\) and \(K_{1, 4}\)-free contains a Hamiltonian path ⋮ Dominating sets and Hamiltonicity in \(K_{1,3}\)-free graphs ⋮ Uniformly Connected Graphs — A Survey ⋮ Edge bounds in nonhamiltonian \(k\)-connected graphs ⋮ The shuffle exchange network has a Hamiltonian path ⋮ Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey ⋮ A sharp Ore-type condition for a connected graph with no induced star to have a Hamiltonian path ⋮ Hamiltonian and long paths in bipartite graphs with connectivity ⋮ Hamilton-connected, vertex-pancyclic and bipartite holes ⋮ Oriented discrepancy of Hamilton cycles ⋮ Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions ⋮ Hamiltonicity, pancyclicity, and full cycle extendability in multipartite tournaments ⋮ Automated conjecturing. III. Property-relations conjectures ⋮ Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy ⋮ 2-Trees: Structural insights and the study of Hamiltonian paths ⋮ A new closure concept preserving graph Hamiltonicity and based on neighborhood equivalence ⋮ Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited ⋮ A note on Hamiltonian cycles in planar graphs ⋮ Bipanconnectivity of faulty hypercubes with minimum degree ⋮ Sufficient Conditions for a Connected Graph to Have a Hamiltonian Path ⋮ Hamiltonicity in Split Graphs - A Dichotomy ⋮ On 2-factors with a bounded number of odd components ⋮ Hamiltonian properties of locally connected graphs with bounded vertex degree ⋮ Recent advances on the Hamiltonian problem: survey III ⋮ Bipartite Kneser graphs are Hamiltonian ⋮ Unnamed Item ⋮ Bipartite Kneser graphs are Hamiltonian ⋮ How many conjectures can you stand? A survey ⋮ The shuffle exchange network has a Hamiltonian path ⋮ COMPARISON OF SUFFICIENT DEGREE BASED CONDITIONS FOR HAMILTONIAN GRAPH ⋮ Some problems on Cayley graphs ⋮ New sufficient condition and Hamiltonian and traceable ⋮ Toughness threshold for the existence of 2-walks in \(K_{4}\)-minor-free graphs ⋮ Graph invariants and large cycles: a survey ⋮ Pancyclicity of Hamiltonian and highly connected graphs ⋮ On a generalization of Chvátal's condition giving new Hamiltonian degree sequences ⋮ Hamilton cycles in strong products of graphs ⋮ A clique-covering sufficient condition for hamiltonicity of graphs ⋮ Hamiltonian and long cycles in bipartite graphs with connectivity ⋮ Unnamed Item ⋮ Induced nets and Hamiltonicity of claw-free graphs ⋮ Hamiltonian threshold for strong products of graphs ⋮ The H-force sets of the graphs satisfying the condition of Ore's theorem ⋮ Normal Eulerian clique-covering and hamiltonicity ⋮ 2-factors with \(k\) cycles in Hamiltonian graphs ⋮ On the hamiltonicity of the Cartesian product ⋮ Combinatorial families that are exponentially far from being listable in Gray code sequence ⋮ Domination number and neighbourhood conditions ⋮ On a Goodman – Hedetniemi Sufficient Condition for the Graph Hamiltonicity ⋮ AN ALGORITHM FOR FINDING LONGEST CYCLES IN CERTAIN BIPARTITE GRAPHS ⋮ Locally pancyclic graphs ⋮ An explicit construction of graphs of bounded degree that are far from being Hamiltonian ⋮ The antipodal layers problem

Cites Work