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 条

[41] Hyper-Hamilton laceable and caterpillar-spannable product graphs
Lewinter, M
Widulski, W
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1997, 34 (11) : 99 - 104
[42] Edge bounds in nonhamiltonian k-connected graphs
Byer, Owen D.
Smeltzer, Deirdre L.
DISCRETE MATHEMATICS, 2007, 307 (13) : 1572 - 1579
[43] On cubic 2-independent Hamiltonian connected graphs
Tung-Yang Ho
Chun-Nan Hung
Lih-Hsing Hsu
Journal of Combinatorial Optimization, 2007, 14 : 275 - 294
[44] A note on 3-connected cubic planar graphs
Lu, Xiaoyun
DISCRETE MATHEMATICS, 2010, 310 (13-14) : 2054 - 2058
[45] Forbidden Pairs for Connected Even Factors in Supereulerian Graphs
Wang, Panpan
Xiong, Liming
GRAPHS AND COMBINATORICS, 2023, 39 (04)
[46] On cubic 2-independent Hamiltonian connected graphs
Ho, Tung-Yang
Hung, Chun-Nan
Hsu, Lih-Hsing
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2007, 14 (2-3) : 275 - 294
[47] Construction of Hamiltonian cycles in layered cubic planar graphs
Franzblau, DS
GRAPHS AND COMBINATORICS, 2002, 18 (02) : 259 - 270
[48] Algorithmic complexity of weakly connected Roman domination in graphs
Chakradhar, Padamutham
Reddy, Palagiri Venkata Subba
Himanshu, Khandelwal
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2022, 14 (03)
[49] A study on degree characterization for hamiltonian-connected graphs
Su, Hsun
Shih, Yuan-Kang
Chen, Shih-Yan
Kao, Shin-Shin
ARS COMBINATORIA, 2017, 133 : 297 - 316
[50] Hamiltonian cycles in linear-convex supergrid graphs
Hung, Ruo-Wei
DISCRETE APPLIED MATHEMATICS, 2016, 211 : 99 - 112

← 1 2 3 4 5 →