The paths embedding of the arrangement graphs with prescribed vertices in given position

Yuan-Hsiang Teng, Jiann-Mean Tan, Chey-Woei Tsay, Lih-Hsing Hsu

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

Let n and k be positive integers with n-ka parts per thousand yen2. The arrangement graph A (n,k) is recognized as an attractive interconnection networks. Let x, y, and z be three different vertices of A (n,k) . Let l be any integer with . We shall prove the following existance properties of Hamiltonian path: (1) for n-ka parts per thousand yen3 or (n,k)=(3,1), there exists a Hamiltonian path R(x,y,z;l) from x to z such that d (R(x,y,z;l))(x,y)=l; (2) for n-k=2 and na parts per thousand yen5, there exists a Hamiltonian path R(x,y,z;l) except for the case that x, y, and z are adjacent to each other.
Original languageEnglish
Pages (from-to)627-646
Number of pages10
JournalJournal of Combinatorial Optimization
Volume24
Issue number4
DOIs
StatePublished - Sep 2012

Keywords

  • Arrangement graph; Panpositionable Hamiltonian; Panconnected; Interconnection network

Fingerprint Dive into the research topics of 'The paths embedding of the arrangement graphs with prescribed vertices in given position'. Together they form a unique fingerprint.

Cite this