Title: Panpositionable hamiltonicity and panconnectivity of the arrangement graphs
Authors: Teng, Yuan-Hsiang
Tan, Jimmy J. M.
Hsu, Lih-Hsing
資訊工程學系
Department of Computer Science
Keywords: arrangement graph;panpositionable hamiltonian;panconnected;interconnection network
Issue Date: 15-Apr-2008
Abstract: The arrangement graph A(n,k) is a generalization of the star graph. It is more flexible in its size than the star graph. There are some results concerning hamiltonicity and pancyclicity of the arrangement graphs. In this paper, we propose a new concept called panpositionable hamiltonicity. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and for any integer l satisfying d(x,y) <= l <= vertical bar v(G)vertical bar - d(x,y), there exists a hamiltonian cycle C of G such that the relative distance between x and y on C is l. A graph G is panconnected if there exists a path of length l joining any two different vertices x and y with d(x,y) <= l <= vertical bar v(G)vertical bar - 1. We show that An, k is panpositionable hamiltonian and panconnected if k >= 1 and n - k >= 2. (c) 2007 Elsevier Inc. All rights reserved.
URI: http://dx.doi.org/10.1016/j.amc.2007.08.073
http://hdl.handle.net/11536/9453
ISSN: 0096-3003
DOI: 10.1016/j.amc.2007.08.073
Journal: APPLIED MATHEMATICS AND COMPUTATION
Volume: 198
Issue: 1
Begin Page: 414
End Page: 432
Appears in Collections:Articles


Files in This Item:

  1. 000254254300037.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.