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

被引：1

作者：

Cheriyan, Joseph ^{[1
]}

Hajebi, Sepehr ^{[1
]}

Qu, Zishen ^{[1
]}

Spirkl, Sophie ^{[1
]}

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

来源：

DISCRETE MATHEMATICS | 2022年 / 345卷 / 07期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Hamiltonicity; Induced subgraphs; Split graphs;

D O I：

10.1016/j.disc.2022.112869

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In 1981, Duffus, Gould, and Jacobson showed that every connected graph either has a Hamiltonian path, or contains a claw (K-1,K-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.& nbsp;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. (C)& nbsp;2022 Elsevier B.V. All rights reserved.

引用

页数：5

共 7 条

[1] Minimal 2-connected non-hamiltonian claw-free graphs [J].

Brousek, J .

DISCRETE MATHEMATICS, 1998, 191 (1-3) :57-64

[2]

CHARTRAND G, 1967, ANN I H POINCARE B, V3, P433

[3] A characterization of 2-connected {K1,3, N3,1,1}-free non-Hamiltonian graphs [J].

Chiba, Shuya ;

Furuya, Michitaka .

DISCRETE MATHEMATICS, 2021, 344 (05)

[4]

Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6

[5] Minimal k-Connected Non-Hamiltonian Graphs [J].

Ding, Guoli ;

Marshall, Emily .

GRAPHS AND COMBINATORICS, 2018, 34 (02) :289-312

[6]

Duffus D., 1981, The theory and applications of graphs: fourth international conference, P297

[7] HAMILTONICITY IN CLAW-FREE GRAPHS [J].

SHEPHERD, FB .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1991, 53 (02) :173-194

← 1 →