標題: Pseudo-Hamiltonian-connected graphs
作者: Chang, GJ
Zhu, XD
應用數學系
Department of Applied Mathematics
關鍵字: pseudo-Hamiltonian-connected;regular Hamiltonian walk;pseudo-edge;vertex packing;regularizable
公開日期: 30-Mar-2000
摘要: 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.
URI: http://hdl.handle.net/11536/30641
ISSN: 0166-218X
期刊: DISCRETE APPLIED MATHEMATICS
Volume: 100
Issue: 3
起始頁: 145
結束頁: 153
Appears in Collections:Articles


Files in This Item:

  1. 000085127900001.pdf

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.