Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

Joseph Cheriyan; Sepehr Hajebi; Zishen Qu; Sophie Spirkl

doi:10.1016/j.disc.2022.112869

Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

Joseph Cheriyan, Sepehr Hajebi, Zishen Qu, Sophie Spirkl

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

In 1981, Duffus, Gould, and Jacobson showed that every connected graph either has a Hamiltonian path, or contains a claw (K_1,3) or a net (a fixed six-vertex graph) as an induced subgraph. This implies that subject to being connected, these two are the only minimal (under taking induced subgraphs) graphs with no Hamiltonian path. Brousek (1998) characterized the minimal graphs that are 2-connected, non-Hamiltonian and do not contain the claw as an induced subgraph. We characterize the minimal graphs that are 2-connected and non-Hamiltonian for two classes of graphs: (1) split graphs, (2) triangle-free graphs. We remark that testing for Hamiltonicity is NP-hard in both classes.

Original language	English (US)
Article number	112869
Journal	Discrete Mathematics
Volume	345
Issue number	7
DOIs	https://doi.org/10.1016/j.disc.2022.112869
State	Published - Jul 2022
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Hamiltonicity
Induced subgraphs
Split graphs

Access to Document

10.1016/j.disc.2022.112869

Cite this

@article{7eacb79770684f429f5e73811620bc57,

title = "Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs",

abstract = "In 1981, Duffus, Gould, and Jacobson showed that every connected graph either has a Hamiltonian path, or contains a claw (K1,3) or a net (a fixed six-vertex graph) as an induced subgraph. This implies that subject to being connected, these two are the only minimal (under taking induced subgraphs) graphs with no Hamiltonian path. Brousek (1998) characterized the minimal graphs that are 2-connected, non-Hamiltonian and do not contain the claw as an induced subgraph. We characterize the minimal graphs that are 2-connected and non-Hamiltonian for two classes of graphs: (1) split graphs, (2) triangle-free graphs. We remark that testing for Hamiltonicity is NP-hard in both classes.",

keywords = "Hamiltonicity, Induced subgraphs, Split graphs",

author = "Joseph Cheriyan and Sepehr Hajebi and Zishen Qu and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",

year = "2022",

month = jul,

doi = "10.1016/j.disc.2022.112869",

language = "English (US)",

volume = "345",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "7",

}

TY - JOUR

T1 - Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

AU - Cheriyan, Joseph

AU - Hajebi, Sepehr

AU - Qu, Zishen

AU - Spirkl, Sophie

PY - 2022/7

Y1 - 2022/7

N2 - In 1981, Duffus, Gould, and Jacobson showed that every connected graph either has a Hamiltonian path, or contains a claw (K1,3) or a net (a fixed six-vertex graph) as an induced subgraph. This implies that subject to being connected, these two are the only minimal (under taking induced subgraphs) graphs with no Hamiltonian path. Brousek (1998) characterized the minimal graphs that are 2-connected, non-Hamiltonian and do not contain the claw as an induced subgraph. We characterize the minimal graphs that are 2-connected and non-Hamiltonian for two classes of graphs: (1) split graphs, (2) triangle-free graphs. We remark that testing for Hamiltonicity is NP-hard in both classes.

AB - In 1981, Duffus, Gould, and Jacobson showed that every connected graph either has a Hamiltonian path, or contains a claw (K1,3) or a net (a fixed six-vertex graph) as an induced subgraph. This implies that subject to being connected, these two are the only minimal (under taking induced subgraphs) graphs with no Hamiltonian path. Brousek (1998) characterized the minimal graphs that are 2-connected, non-Hamiltonian and do not contain the claw as an induced subgraph. We characterize the minimal graphs that are 2-connected and non-Hamiltonian for two classes of graphs: (1) split graphs, (2) triangle-free graphs. We remark that testing for Hamiltonicity is NP-hard in both classes.

KW - Hamiltonicity

KW - Induced subgraphs

KW - Split graphs

UR - http://www.scopus.com/inward/record.url?scp=85125674180&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85125674180&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2022.112869

DO - 10.1016/j.disc.2022.112869

M3 - Article

AN - SCOPUS:85125674180

SN - 0012-365X

VL - 345

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 7

M1 - 112869

ER -

Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this