Is there a name for graphs with the following property?

213 Views Asked by At

The property of the graph is the following: For any vertex, there is a hamiltonian path starting with this vertex, but the graph is not hamiltonian. The following graph is a small example: example graph

Important examples are hypohamiltonian graphs (deleting each vertex leads to a hamiltonian graph, but the graph is not hamiltonian ; for example the Petersen graph)

  • Is there a name for such graphs?
  • Which numbers of vertices are possible for such a graph?
  • Is there a knight graph with this property? (See mathworld knight graph for more details. I think the answer is no.)
1

There are 1 best solutions below

0
On BEST ANSWER

These are homogeneously traceable non-hamiltonian graphs.

See e.g. "On homogeneously traceable nonhamiltonian graphs" (Gary Chartrand, Ronald J. Gould, S. F. Kapoor, 1979). In this paper they "construct, for each integer $p > 9$, a homogeneously traceable nonhamiltonian graph of order $p$" and prove that there are none with 3 to 8 vertices.

It was abbreviated as NHHT in the 2007 paper "Nontraceable detour graphs" (DOI 10.1016/j.disc.2006.07.019):

The study of nonhamiltonian, homogeneously traceable graphs (NHHT graphs) was initiated by Skupień in 1975...