dc.contributor.author | Chaniotis, Aristotelis | |
dc.contributor.author | Qu, Zishen | |
dc.contributor.author | Spirkl, Sophie | |
dc.date.accessioned | 2023-02-21 19:49:45 (GMT) | |
dc.date.available | 2023-02-21 19:49:45 (GMT) | |
dc.date.issued | 2022-12-29 | |
dc.identifier.uri | https://doi.org/10.1016/j.disc.2022.113289 | |
dc.identifier.uri | http://hdl.handle.net/10012/19176 | |
dc.description.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 -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. | en |
dc.description.sponsorship | Natural Sciences and Engineering Research Council of Canada (NSERC), RGPIN-2020-03912 | en |
dc.language.iso | en | en |
dc.publisher | Elsevier ScienceDirect | en |
dc.relation.ispartofseries | Discrete Mathematics;113289 | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 International | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | hamiltonicity | en |
dc.subject | induced subgraphs | en |
dc.subject | wheel | en |
dc.title | Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs | en |
dc.type | Article | en |
dcterms.bibliographicCitation | Chaniotis, A., Qu, Z., & Spirkl, S. (2022). Minimal induced subgraphs of the class of 2-connected non-hamiltonian wheel-free graphs. Discrete Mathematics, 346(3), 113289. https://doi.org/10.1016/j.disc.2022.113289 | en |
uws.contributor.affiliation1 | Faculty of Mathematics | en |
uws.contributor.affiliation2 | Combinatorics and Optimization | en |
uws.typeOfResource | Text | en |
uws.peerReviewStatus | Reviewed | en |
uws.scholarLevel | Faculty | en |