Minimal k-connected non-Hamiltonian graphs
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.
- A note on Hamiltonian circuits
- A Theorem on Planar Graphs
- Construction of planar 4-connected triangulations
- Decomposition of regular matroids
- Graph minors. IX: Disjoint crossed paths
- Hamilton cycles in plane triangulations
- Hamiltonicity of planar graphs with a forbidden minor
- scientific article; zbMATH DE number 3317672 (Why is no real title available?)
- Minimal 2-connected non-Hamiltonian claw-free graphs
- The circumference of a graph with no \(K_{3,t}\)-minor. II
- Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs
- Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs
- Non-Hamiltonian graphs in which every edge-contracted subgraph is Hamiltonian
- scientific article; zbMATH DE number 3912418 (Why is no real title available?)
- scientific article; zbMATH DE number 4118386 (Why is no real title available?)
This page was built for publication: Minimal \(k\)-connected non-Hamiltonian graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1743684)
