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 条

[31] Globally bi-3*-connected graphs
Kao, Shin-Shin
Hsu, Hong-Chun
Hsu, Lih-Hsing
DISCRETE MATHEMATICS, 2009, 309 (08) : 1931 - 1946
[32] Complexity of coloring graphs without paths and cycles
Hell, Pavol
Huang, Shenwei
DISCRETE APPLIED MATHEMATICS, 2017, 216 : 211 - 232
[33] Hamiltonicity of 6-connected line graphs
Zhan, Mingquan
DISCRETE APPLIED MATHEMATICS, 2010, 158 (17) : 1971 - 1975
[34] 4-connected projective-planar graphs are hamiltonian-connected
Kawarabayashi, Ken-ichi
Ozeki, Kenta
PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013), 2013, : 378 - 395
[35] Global cycle properties of locally isometric graphs
Borchert, Adam
Nicol, Skylar
Oellermann, Ortrud R.
DISCRETE APPLIED MATHEMATICS, 2016, 205 : 16 - 26
[36] An Essential, Hyperconnected, Local Geometric Morphism that is not Locally Connected
Hemelaer, Jens
Rogers, Morgan
APPLIED CATEGORICAL STRUCTURES, 2021, 29 (04) : 573 - 576
[37] On open mappings of locally connected continua onto arcs
Charatonik, JJ
Charatonik, WJ
Miklos, S
Spyrou, P
HOUSTON JOURNAL OF MATHEMATICS, 1998, 24 (01): : 21 - 43
[38] An Essential, Hyperconnected, Local Geometric Morphism that is not Locally Connected
Jens Hemelaer
Morgan Rogers
Applied Categorical Structures, 2021, 29 : 573 - 576
[39] Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ✩
Wang, Cai-Xia
Yang, Yu
Xu, Shou-Jun
THEORETICAL COMPUTER SCIENCE, 2023, 957
[40] List-coloring squares of sparse subcubic graphs
Dvorak, Zdenek
Skrekovski, Riste
Tancer, Martin
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (01) : 139 - 159

← 1 2 3 4 5 →