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 \geq 2\)) graph of order \(n\) and \(\max\{d(v) : v \in S\} \geq \frac{n}{2}\) for every independent set \(S\) of \(G\) with \(|S| = k\) which has two distinct vertices \(x, y \in S\) satisfying \(1\leq |N(x) \cap N(y)| \leq \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.