Pseudo-Hamiltonian-connected graphs (Q1971217)

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.