Pseudo-Hamiltonian-connected graphs
type: Item
instance of: scholarly article
title: Pseudo-Hamiltonian-connected graphs
zbMATH Open document ID: 0939.05054
DOI: 10.1016/S0166-218X(99)00181-X
published in: Discrete Applied Mathematics
publication date: 2000-06-29T00:00:00Z
review text: A graph \(G\) is called pseudo-\(k\) Hamiltonian-connected if the associated graph \(G[k]\) (obtained from \(G\) by replacing every vertex by an independent set of \(k\geq 1\) vertices) is Hamiltonian-connected. The main result says that certain six statements are equivalent, where one of them is the question of pseudo-Hamiltonian-connectedness and another concerns a beetle problem posed by R. Nowakowski. This characterization and its proof provide a polynomial time algorithm answering these questions. The studied problems are related to several other notions (vertex packing, Berge's regularizability, 2-bicriticality, and toughness). The NP-hardness of an efficient beetle problem is proved.
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1421663
zbMATH Keywords: pseudo-Hamiltonian connected
zbMATH Keywords: regular Hamiltonian walk
zbMATH Keywords: beetle problem
zbMATH Keywords: vertex packing
zbMATH Keywords: regularizability
author: Gerard Jennhwa Chang
author: Xuding Zhu
MaRDI profile type: Publication
cites work: Regularisable Graphs
cites work: Tough graphs and Hamiltonian circuits.
cites work: Toughness and the existence ofk-factors
cites work: Vertex packings: Structural properties and algorithms
cites work: On the integer-valued variables in the linear vertex packing problem
cites work: Q3325758
cites work: Minimum node covers and 2-bicritical graphs
Wikidata QID: Q126671684
description: scientific article; zbMATH DE number 1421663