Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs

DOI10.1016/J.DISC.2022.113289zbMATH Open1506.05112arXiv2204.07671OpenAlexW4313325064MaRDI QIDQ2111937FDOQ2111937

Zishen Qu, Aristotelis Chaniotis, Sophie Spirkl

Publication date: 17 January 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Given a graph $G$ and a graph property $P$ we say that $G$ is minimal with respect to $P$ if no proper induced subgraph of $G$ has the property $P$. An HC-obstruction is a minimal 2-connected non-Hamiltonian graph. Given a graph $H$, a graph $G$ is $H$-free if $G$ has no induced subgraph isomorphic to $H$. The main motivation for this paper originates from a theorem of Duffus, Gould, and Jacobson (1981), which characterizes all the minimal connected graphs with no Hamiltonian path. In 1998, Brousek characterized all the claw-free HC-obstructions. On a similar note, Chiba and Furuya (2021), characterized all (not only the minimal) 2-connected non-Hamiltonian $K_{1,3},N_{3,1,1}$-free graphs. Recently, Cheriyan, Hajebi, and two of us (2022), characterized all triangle-free HC-obstructions and all the HC-obstructions which are split graphs. A wheel is a graph obtained from a cycle by adding a new vertex with at least three neighbors in the cycle. In this paper we characterize all the HC-obstructions which are wheel-free graphs.

Full work available at URL: https://arxiv.org/abs/2204.07671

Recommendations

• Minimal \(2\)-connected non-Hamiltonian claw-free graphs
• Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs
• Forbidden triples for Hamiltonicity
• Wheel-free planar graphs
• A characterization of 2-connected \(\{ K_{1 , 3} , N_{3 , 1 , 1} \}\)-free non-Hamiltonian graphs

zbMATH Keywords

induced subgraphswheelHamiltonicity

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Connectivity (05C40)

Cites Work

• On graphs with no induced subdivision of \(K_4\)
• Hamiltonicity in claw-free graphs
• Minimal \(2\)-connected non-Hamiltonian claw-free graphs
• Graph Theory
• Topology of series-parallel networks
• Title not available (Why is that?)
• Edge-colouring and total-colouring chordless graphs
• A characterization of 2-connected \(\{ K_{1 , 3} , N_{3 , 1 , 1} \}\)-free non-Hamiltonian graphs
• Minimal \(k\)-connected non-Hamiltonian graphs
• Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs

This page was built for publication: Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111937)