Hamiltonian path saturated graphs with small size

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