Hamilton cycles in sparse locally connected graphs

被引：3

作者：

van Aardt, Susan A. ^{[1
]}

Burger, Alewyn P. ^{[2
]}

Frick, Marietjie ^{[3
]}

Thomassen, Carsten ^{[4
]}

de Wet, Johan P. ^{[3
,5
]}

机构：

[1] Univ South Africa, UNISA, Dept Math Sci, POB 392, ZA-0003 Pretoria, South Africa

[2] Univ Stellenbosch, Dept Logist, Private Bag X1, ZA-7602 Matieland, South Africa

[3] Univ Pretoria, Dept Math & Appl Math, Private Bag X20, ZA-0028 Hatfield, South Africa

[4] Tech Univ Denmark, Dept Appl Math & Comp Sci, DK-2800 Lyngby, Denmark

[5] DST NRF Ctr Excellence Math & Stat Sci CoE MaSS, Johannesburg, South Africa

来源：

DISCRETE APPLIED MATHEMATICS | 2019年 / 257卷

基金：

新加坡国家研究基金会;

关键词：

Locally connected; Hamiltonian; NP-complete; Polynomial time algorithm;

D O I：

10.1016/j.dam.2018.10.031

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A graph G is locally connected if for every nu is an element of V(G) the open neighbourhood N(nu) of nu is nonempty and induces a connected graph in G. We characterize locally connected graphs of order n with less than 2n edges and show that for any natural number k the Hamilton Cycle Problem for locally connected graphs of order n with m edges is polynomially solvable if m <= 2n + k log(2) n, but NP-complete if m = 2n + [n(1/k)]. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：276 / 288

页数：13

共 50 条

[21] Cubic 1-fault-tolerant hamiltonian graphs, Globally 3*-connected graphs, and Super 3-spanning connected graphs
Kao, Shin-Shin
Huang, Hua-Min
Hsu, Kung-Ming
Hsu, Lih-Hsing
ARS COMBINATORIA, 2013, 110 : 301 - 322
[22] Hamiltonicity of Connected Domination Critical Graphs
Kaemawichanurat, P.
Caccetta, L.
Ananchuen, W.
ARS COMBINATORIA, 2018, 136 : 127 - 151
[23] Hamiltonicity of 4-connected graphs
Hao Li
Feng Tian
Zhi Xia Xu
Acta Mathematica Sinica, English Series, 2010, 26 : 699 - 710
[24] Pancyclicity of Hamiltonian and highly connected graphs
Keevash, Peter
Sudakov, Benny
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2010, 100 (05) : 456 - 467
[25] Hamiltonicity of 4-connected graphs
Li, Hao
Tian, Feng
Xu, Zhi Xia
ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2010, 26 (04) : 699 - 710
[26] Hamiltonicity of 4-connected Graphs
Hao LI LRI
ActaMathematicaSinica(EnglishSeries), 2010, 26 (04) : 699 - 710
[27] Mutually orthogonal hamiltonian connected graphs
Ho, Tung-Yang
Lin, Cheng-Kuan
Tan, Jimmy J. M.
Hsu, Lih-Hsing
APPLIED MATHEMATICS LETTERS, 2009, 22 (09) : 1429 - 1431
[28] Hardness Results of Connected Power Domination for Bipartite Graphs and Chordal Graphs
Goyal, Pooja
Panda, B. S.
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2021, 2021, 13135 : 653 - 667
[29] Connected [1,2]-Sets in Graphs
Zhang, Chao
Zhao, Chengye
THEORETICAL COMPUTER SCIENCE (NCTCS 2018), 2018, 882 : 93 - 98
[30] Linear separation of connected dominating sets in graphs
Chiarelli, Nina
Milanic, Martin
ARS MATHEMATICA CONTEMPORANEA, 2019, 16 (02) : 487 - 525

← 1 2 3 4 5 →