NEIGHBORHOOD UNIONS AND A GENERALIZATION OF DIRACS THEOREM

Dirac proved that if each vertex of a graph G of order n greater-than-or-equal-to 3 has degree at least n/2, then the graph is Hamiltonian. This result will be generalized by showing that if the union of the neighborhoods of each pair of vertices of a 2-connected graph G of sufficiently large order n has at least n/2 vertices, then G is Hamiltonian. Other results that are based on neighborhood unions of pairs of vertices will be proved that give the existence of cycles, paths and matchings. Also, Hamiltonian results will be considered that use the union of neighborhoods of more than 2 vertices.