The H-force sets of the graphs satisfying the condition of Ore's theorem

DOI10.1515/MATH-2020-0039MaRDI QIDQ2053412zbMATH OpenOpenAlexFDO

Authors Ruijuan Li, Xinhong Zhang

Publication date 29 November 2021

Published in Open Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

H-force numberH-force setOre's theoremweak closure

Mathematics Subject Classification ID

Vertex degrees (05C07) Eulerian and Hamiltonian graphs (05C45)

Abstract: Let $G$ be a Hamiltonian graph with $n$ vertices. A nonempty vertex set $XsubseteqV(G)$ is called a Hamiltonian cycle enforcing set (in short, an $H$-force set) of $G$ if every $X$-cycle of $G$ (i.e., a cycle of $G$ containing all vertices of $X$) is a Hamiltonian cycle. For the graph $G$, $h(G)$ is the smallest cardinality of an $H$-force set of $G$ and call it the $H$-force number of $G$. Ore's theorem states that the graph $G$ is Hamiltonian if $d(u)+d(v)geqn$ for every pair of nonadjacent vertices $u,v$ of $G$. In this paper, we study the $H$-force sets of the graphs satisfying the condition of Ore's theorem, show that the $H$-force number of these graphs is possibly $n$, or $n-2$, or $fracn2$ and give a classification of these graphs due to the $H$-force number.

Recommendations

• On vertices enforcing a Hamiltonian cycle
• On the H-force number of Hamiltonian graphs and cycle extendability
• Enforced Hamiltonian cycles in circulant graphs
• Enforced Hamiltonian cycles in generalized dodecahedra
• The \(H\)-force set of a hypertournament

Cites work

• \(H\)-force sets of locally semicomplete digraphs
• Advances on the Hamiltonian problem -- a survey
• An efficient condition for a graph to be Hamiltonian
• New sufficient conditions for cycles in graphs
• Note on Hamilton Circuits
• On vertices enforcing a Hamiltonian cycle
• Some Theorems on Abstract Graphs
• The \(H\)-force set of a hypertournament
• Updating the hamiltonian problem—A survey

Cited in

(8)

• H-forming sets in graphs
• The \(H\)-force set of a hypertournament
• On vertices enforcing a Hamiltonian cycle
• The graph constructions ofHaj�s and Ore
• On the H-force number of Hamiltonian graphs and cycle extendability
• Enforced Hamiltonian cycles in generalized dodecahedra
• Enforced Hamiltonian cycles in circulant graphs
• \(H\)-force sets of locally semicomplete digraphs

This page was built for publication: The H-force sets of the graphs satisfying the condition of Ore's theorem

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