Hamiltonian path saturated graphs with small size Original Research Article

A graph G is said to be hamiltonian path saturated (HPS for short), if G has no hamiltonian path but any addition of a new edge in G creates a hamiltonian path in G. It is known that an HPS graph of order n has size at most image and, for image, the only HPS graph of order n and size image is image. Denote by image the minimum size of an HPS graph of order n. We prove that image. Using some properties of Isaacs’ snarks we give, for every image, an HPS graph image of order n and size image. This proves image for image. We also consider image-path cover saturated graphs and image-saturated graphs with small size.