What is the term for a graph in which each edge belongs to a Hamiltonian cycle?

Question

Furthermore, are they any known results about these graphs, such as necessary or sufficient conditions for a graph to have this property?

Answer 1

A slightly stronger condition is that for any two vertices $s,t$ (whether or not $st$ is an edge) there is a Hamiltonian path starting at $s$ and ending at $t$, and such graphs are called Hamiltonian connected.

(All Hamiltonian connected graphs have your property as well: if $st$ is an edge, then the Hamiltonian $s,t$-path together with that edge forms a Hamiltonian cycle connecting $st$. The reverse is not necessarily true.)

Many of the Bondy–Chvátal-type theorems (such as Dirac's theorem and Ore's theorem) for Hamiltonian cycles generalize to prove that a graph is Hamiltonian connected, or to prove your condition. For example, here is a very general result:

Let $G = (X,E)$ be a simple graph of order $n$ with degrees $d_1 \le d_2 \le \dots \le d_n$. Let $q$ be an integer, $0 \le q \le n-3$. If, for every $k$ with $q < k < \frac12(n+q)$, the following condition holds: $$d_{k-q} \le k \implies d_{n-k} \ge n-k+q$$ then for each subset $F$ of edges with $|F|=q$ such that the connected components of $(X,F)$ are paths, there exists a Hamiltonian cycle of $G$ that contains $F$.

Furthermore, this result is the best possible in the following sense: each sequence of degrees that does not satisfy the condition above is majorized by a sequence of degrees of a graph that does not have the desired property.

Take $q=1$ and the property in the theorem is exactly the property you want.

This is Theorem 8 in Chapter 10 of Berge's Graphs and Hypergraphs, which follows it by a list of many corollaries you may also be interested in.