Panpositionable hamiltonicity and panconnectivity of the arrangement graphs

Yuan-Hsiang Teng, Jiann-Mean Tan, Lih-Hsing Hsu

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

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.
Original languageEnglish
Pages (from-to)414-432
Number of pages19
JournalApplied Mathematics and Computation
Volume198
Issue number1
DOIs
StatePublished - 15 Apr 2008

Keywords

  • arrangement graph; panpositionable hamiltonian; panconnected; interconnection network

Fingerprint Dive into the research topics of 'Panpositionable hamiltonicity and panconnectivity of the arrangement graphs'. Together they form a unique fingerprint.

Cite this