Hamiltonian path saturated graphs with small size

AbstractA 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 (n-12) and, for n⩾6, the only HPS graph of order n and size (n-12) is Kn-1∪K1. Denote by sat(n,HP) the minimum size of an HPS graph of order n. We prove that sat(n,HP)⩾⌊(3n-1)/2⌋-2. Using some properties of Isaacs’ snarks we give, for every n⩾54, an HPS graph Gn of order n and size ⌊(3n-1)/2⌋. This proves sat(n,HP)⩽⌊(3n-1)/2⌋ for n⩾54. We also consider m-path cover saturated graphs and Pm-saturated graphs with small size