Notes on Hamiltonian Graphs and Hamiltonian-Connected Graphs

Abstract

Let $G=(V(G),E(G))$ be a graph and $\alpha (G)$ be the independence number of $G$. For a vertex $v\in V(G)$, $d(v)$ and $N(v)$ represent the degree and the neighborhood of $v$ in $G$, respectively.In this paper, we prove that if $G$ is a $k$-connected graph of order $n$, where ($k\ge 2$) graph of order $n$ and $max\{d(v):v\in S\}\ge \frac{n}{2}$ for every independent set $S$ of $G$ with $|S|=k$ which has two distinct vertices $x,y\in S$ satisfying $1\le |N(x)\cap N(y)|\le \alpha (G)–2,$
then either $G$ is hamiltonian or else $G$ belongs to one of a family of exceptional graphs.We also establish a similar sufficient condition for Hamiltonian-connected graphs.