Pseudo-Hamiltonian-connected graphs

Pseudo-Hamiltonian-connected graphs

0.00 Avg rating0 Votes
Article ID: iaor20013535
Country: Netherlands
Volume: 100
Issue: 3
Start Page Number: 145
End Page Number: 153
Publication Date: Mar 2000
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: game theory
Abstract:

Given a graph G and a positive integer k, denote by G[k] the graph obtained from G by replacing each vertex of G with an independent set of size k. A graph G is called pseudo-k Hamiltonian-connected if G[k] is Hamiltonian-connected, i.e., every two distinct vertices of G[k] are connected by a Hamiltonian path. A graph G is called pseudo Hamiltonian-connected if it is pseudo-k Hamiltonian-connected for some positive integer k. This paper proves that a graph G is pseudo-Hamiltonian-connected if and only if for every non-empty proper subset X of V(G), |N(X)|>|X|. The proof of the characterization also provides a polynomial-time algorithm that decides whether or not a given graph is pseudo-Hamiltonian-connected. The characterization of pseudo-Hamiltonian-connected graphs also answers a question of Richard Nowakowski, which motivated this paper.

Reviews

Required fields are marked *. Your email address will not be published.