Neighbourhood unions and Hamiltonian properties in graphs (Q1123212): Difference between revisions

We investigate the relationship between the cardinality of the union of the neighborhoods of an arbitrary pair of nonadjacent vertices and various Hamiltonian type properties in graphs. In particular, we show that if G is 2-connected, of order \(p\geq 3\) and if for every pair of nonadjacent vertices x and y: a) \(| N(x)\cup N(y)| \geq (p-1)/2\), then G is traceable, b) \(| N(x)\cup N(y)| \geq (2p-1)/3\), then G is Hamiltonian, and c) if G is 3-connected and \(| N(x)\cup N(y)| >2p/3\), then G is Hamiltonian-connected.