Panpositionable hamiltonicity and panconnectivity of the arrangement graphs

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 hamilto...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematics and computation 2008-04, Vol.198 (1), p.414-432
Main Authors: Teng, Yuan-Hsiang, Tan, Jimmy J.M., Hsu, Lih-Hsing
Format: Article
Language:English
Subjects:
Arrangement graph
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Interconnection network
Mathematical analysis
Mathematics
Numerical analysis
Numerical analysis. Scientific computation
Panconnected
Panpositionable hamiltonian
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ⩽ | V ( G ) | - 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 ⩽ | V ( G ) | - 1 . We show that A n, k is panpositionable hamiltonian and panconnected if k ⩾ 1 and n − k ⩾ 2.
ISSN:0096-3003
1873-5649
DOI:10.1016/j.amc.2007.08.073