Department of Applied Mathematics
|關鍵字:||pseudo-Hamiltonian-connected;regular Hamiltonian walk;pseudo-edge;vertex packing;regularizable|
|摘要:||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. (C) 2000 Elsevier Science B.V. All rights reserved.|
|期刊:||DISCRETE APPLIED MATHEMATICS|
|Appears in Collections:||Articles|
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.