New Sufficient Conditions for $s$-Hamiltonian Graphs and $s$-Hamiltonian Connected Graphs

Abstract

A graph $G$ is $s$-Hamiltonian if for any $S\subseteq V(G)$ of order at most $s$, $G-S$ has a Hamiltonian cycle, and $s$-Hamiltonian connected if for any $S\subseteq V(G)$ of order at most $s$, $G-S$ is Hamiltonian-connected. Let $k>0,s\ge 0$ be two integers. The following are proved in this paper:(1) Let $k\ge s+2$ and $s\le n-3$. If $G$ is a $k$-connected graph of order $n$ and if $max\{d(v):v\in I\}\ge (n+s)/2$ for every independent set $I$ of order $k-s$ such that $I$ has two distinct vertices $x,y$ with $1\le |N(x)\cap N(y)|\le \alpha (G)+s-1$, then $G$ is $s$-Hamiltonian.(2) Let $k\ge s+3$ and $s\le n-2$. If $G$ is a $k$-connected graph of order $n$ and if $max\{d(v):v\in I\}\ge (n+s+1)/2$ for every independent set $I$ of order $k-s-1$ such that $I$ has two distinct vertices $x,y$ with $1\le |N(x)\cap N(y)|\le \alpha (G)+s$, then $G$ is $s$-Hamiltonian connected.These results extend several former results by Dirac, Ore, Fan, and Chen.