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 条

[1] A NOTE ON CYCLES IN LOCALLY HAMILTONIAN AND LOCALLY HAMILTON-CONNECTED GRAPHS
Tang, Long
Vumar, Elkin
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2020, 40 (01) : 77 - 84
[2] Hamilton cycles in a family of graphs which includes the generalized Petersen graphs
Dean, Matthew
ARS COMBINATORIA, 2012, 103 : 205 - 224
[3] Global cycle properties in locally connected, locally traceable and locally hamiltonian graphs
van Aardt, Susan A.
Frick, Marietjie
Oellermann, Ortrud R.
de Wet, Johan
DISCRETE APPLIED MATHEMATICS, 2016, 205 : 171 - 179
[4] Forbidden Subgraphs and Weak Locally Connected Graphs
Liu, Xia
Lin, Houyuan
Xiong, Liming
GRAPHS AND COMBINATORICS, 2018, 34 (06) : 1671 - 1690
[5] Forbidden Subgraphs and Weak Locally Connected Graphs
Xia Liu
Houyuan Lin
Liming Xiong
Graphs and Combinatorics, 2018, 34 : 1671 - 1690
[6] Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs
Panda, B. S.
Pradhan, D.
INFORMATION PROCESSING LETTERS, 2010, 110 (23) : 1067 - 1073
[7] Hamiltonian properties of almost locally connected claw-free graphs
Chen, Xiaodong
Li, MingChu
Liao, Wei
Broersma, Hajo
ARS COMBINATORIA, 2016, 124 : 95 - 109
[8] Hardness Results of Connected Power Domination for Bipartite Graphs and Chordal Graphs
Goyal, Pooja
Panda, B. S.
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2024, 35 (06) : 669 - 703
[9] On locally connected connectifications
Fedeli, A
Le Donne, A
TOPOLOGY AND ITS APPLICATIONS, 1999, 96 (01) : 85 - 88
[10] CONNECTED COALITIONS IN GRAPHS
Alikhani, Saeid
Bakhshesh, Davood
Golmohammadi, Hamidreza
Konstantinova, Elena v
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, 44 (04) : 1551 - 1566

← 1 2 3 4 5 →