2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.