A New Idea For Hamiltonian Problem

Abstract

Let $G$ be a $2$-connected graph of order $n$ with connectivity $\kappa$ and independence number $\alpha$. In this paper, we show that if for each independent set $S$ with $|S|=k+1$, there are $u,v\in S$ such that satisfying one of the following conditions:

1. $d(u)+d(v)\ge n$; or $|N(u)\cap N(v)|\ge \alpha$; or $|N(u)\cup N(v)|\ge n-k$;
2. for any $x\in \{u,v\}$, $y\in V(G)$ and $d(x,y)=2$, it implies that $max\{d(x),d(y)\}\ge n/2$,

then $G$ is hamiltonian. This result reveals the internal relations among several well-known sufficient conditions: $(1)$ it shows that it does not need to consider all pairs of nonadjacent or distance two vertices in $G$; $(2)$ it makes known that for different pairs of vertices in $G$, it permits to satisfy different conditions.