A localization method in Hamiltonian graph theory

DOI10.1016/J.JCTB.2020.04.005zbMATH Open1459.05148arXiv1810.10430OpenAlexW3100054338MaRDI QIDQ1998767FDOQ1998767

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)

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).

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

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

zbMATH Keywords

Hamilton cycleinfinite graphslocal conditionsHamiltonian curve

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• On the local nature of some classical theorems on Hamilton cycles
• Local Dirac's condition on the existence of 2-factor
• Some localization theorems on Hamiltonian circuits
• On Hamiltonicity of regular graphs with bounded second neighborhoods
• 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)