Minimal \(k\)-connected non-Hamiltonian graphs (Q1743684)

The paper explores the following general problem: what are the minimal \(k\)-connected non-Hamiltonian graphs? What is interesting here is that we can have various definitions for minimality. While a graph is minimal if it does not contain a smaller graph with the same properties, there are many different possibilities: one graph can be contained in another, say subgraphs, induced subgraphs, minors, and induced minors. The paper discusses the problem for \(k\in \{2,3\}\) with respect to the four containment relations mentioned above. For \(k=2\), when the containment relation is minor, the problem is solved and the only minimal graph is \(K_{2,3}\). When the containment relation is subgraph, the problem is also solved and the minimal graphs are \(\theta_{a,b,c}\) for \(a, b, c\geq 2\) where \(\theta_{a,b,c}\) is a theta graph consisting of two distinct vertices and three internally-disjoint paths between them of lengths \(a\), \(b\) and \(c\). When the containment relation is an induced subgraph, \textit{J. Brousek} [Discrete Math. 191, No. 1--3, 57--64 (1998; Zbl 0958.05086)] obtained a solution for claw-free graphs. In this paper, the authors contribute with a solution for the problem when the containment relation is an induced minor, where the minimal graphs in this sense are \(K_{2,3}\) and \(K_{2,3}^+\), which is obtained from \(K_{2,3}\) by adding an edge between the two vertices of degree \(3\). For \(k = 3\), the authors conjectured a set of minimal non-Hamiltonian graphs for the minor relation and they prove one case of this conjecture, that is, every non-Hamiltonian planar triangulation contains the Herschel graph as a minor.