Pseudo-Hamiltonian-connected graphs (Q1971217): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Created claim: Wikidata QID (P12): Q126671684, #quickstatements; #temporary_batch_1719435665696 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q126671684 / rank | |||
Normal rank |
Latest revision as of 23:03, 26 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pseudo-Hamiltonian-connected graphs |
scientific article |
Statements
Pseudo-Hamiltonian-connected graphs (English)
0 references
29 June 2000
0 references
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.
0 references
pseudo-Hamiltonian connected
0 references
regular Hamiltonian walk
0 references
beetle problem
0 references
vertex packing
0 references
regularizability
0 references