pith. sign in

arxiv: 1810.03894 · v1 · pith:DRLKBF57new · submitted 2018-10-09 · 🧮 math.CO

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

classification 🧮 math.CO
keywords forcecyclegraphshamiltoniangraphnumbertheoremvertices
0
0 comments X
read the original abstract

Let $G$ be a Hamiltonian graph with $n$ vertices. A nonempty vertex set $X\subseteq V(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)\geq n$ 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 $\frac{n}{2}$ and give a classification of these graphs due to the $H$-force number.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.