A localization method in Hamiltonian graph theory

DOI10.1016/J.JCTB.2020.04.005MaRDI QIDQ1998767zbMATHOpenAlexFDO

Authors Jonas B. Granholm, N. K. Khachatryan, Armen S. Asratian

Publication date 8 March 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.10430

zbMATH Keywords

Hamilton cycleinfinite graphslocal conditionsHamiltonian curve

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Infinite graphs (05C63)

Abstract: The classical global criteria for the existence of Hamilton cycles only apply to graphs with large edge density and small diameter. In a series of papers Asratian and Khachatryan developed local criteria for the existence of Hamilton cycles in finite connected graphs, which are analogues of the classical global criteria due to Dirac (1952), Ore (1960), Jung (1978), and Nash-Williams (1971). The idea was to show that the global concept of Hamiltonicity can, under rather general conditions, be captured by local phenomena, using the structure of balls of small radii. (The ball of radius $r$ centered at a vertex $u$ is a subgraph of $G$ induced by the set of vertices whose distances from $u$ do not exceed $r$.) Such results are called localization theorems and present a possibility to extend known classes of finite Hamiltonian graphs. In this paper we formulate a general approach for finding localization theorems and use this approach to formulate local analogues of well-known results of Bauer et al. (1989), Bondy (1980), H"aggkvist and Nicoghossian (1981), and Moon and Moser (1963). Finally we extend two of our results to infinite locally finite graphs and show that they guarantee the existence of Hamiltonian curves, introduced by K"undgen, Li and Thomassen (2017).

Recommendations

• Publication:4504844
• scientific article; zbMATH DE number 1187334
• Locally Hamiltonian graphs
• scientific article; zbMATH DE number 4093499
• Hamiltonicity of locally Hamiltonian and locally traceable graphs
• New sufficient localized conditions for Hamiltonian graphs
• scientific article; zbMATH DE number 1545702
• New local conditions for a graph to be Hamiltonian
• The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs
• scientific article; zbMATH DE number 786156

Cites work

• scientific article; zbMATH DE number 4073020 (Why is no real title available?)
• scientific article; zbMATH DE number 1071797 (Why is no real title available?)
• A generalization of a result of Häggkvist and Nicoghossian
• A note on Hamiltonian circuits
• A remark on Hamiltonian cycles
• A short proof of a theorem concerning degree sums and connectivity on Hamiltonian graphs
• A sufficient condition for Hamiltonicity in locally finite graphs
• A sufficient local degree condition for Hamiltonicity in locally finite claw-free graphs
• Advances on the Hamiltonian problem -- a survey
• Cycles through all finite vertex sets in infinite graphs
• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• Extending cycles locally to Hamilton cycles
• Hamilton Cycles in Planar Locally Finite Graphs
• Infinite Hamilton cycles in squares of locally finite graphs
• Locally finite graphs with ends: A topological approach. II: Applications
• New local conditions for a graph to be Hamiltonian
• Note on Hamilton Circuits
• On Hamiltonian bipartite graphs
• On infinite cycles. I, II
• On the local nature of some classical theorems on Hamilton cycles
• Recent advances on the Hamiltonian problem: survey III
• Some Theorems on Abstract Graphs
• Some localization theorems on Hamiltonian circuits
• The existence of a 2-factor in a graph satisfying the local Chvátal-Erdős condition
• The square of every two-connected graph is Hamiltonian

Cited in

(6)

• On the local nature of some classical theorems on Hamilton cycles
• On Hamiltonicity of regular graphs with bounded second neighborhoods
• Local Dirac's condition on the existence of 2-factor
• Some local-global phenomena in locally finite graphs
• Some localization theorems on Hamiltonian circuits
• Local degree conditions for Hamiltonicity of claw-free graphs

This page was built for publication: A localization method in Hamiltonian graph theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1998767)