The panpositionable panconnectedness of augmented cubes

• Published in: Information sciences 2010-10, Vol.180 (19), p.3781-3793
• Main Authors: Kung, Tzu-Liang, Teng, Yuan-Hsiang, Hsu, Lih-Hsing
• Format: Article
• Language: English
• Subjects: Cubes; Graphs; Hamiltonian; Integers; Interconnection network; Panconnected; Pancyclic; Path embedding
• ISSN: 0020-0255; 1872-6291
• DOI: 10.1016/j.ins.2010.06.016

A graph G is panconnected if, for any two distinct vertices x and y of G, it contains an [ x, y]-path of length l for each integer l satisfying d G ( x, y) ⩽ l ⩽ ∣ V( G)∣ − 1, where d G ( x, y) denotes the distance between vertices x and y in G, and V( G) denotes the vertex set of G. For insight into the concept of panconnectedness, we propose a more refined property, namely panpositionable panconnectedness. Let x, y, and z be any three distinct vertices in a graph G. Then G is said to be panpositionably panconnected if for any d G ( x, z) ⩽ l 1 ⩽ ∣ V( G)∣ − d G ( y, z) − 1, it contains a path P such that x is the beginning vertex of P, z is the ( l 1 + 1)th vertex of P, and y is the ( l 1 + l 2 + 1)th vertex of P for any integer l 2 satisfying d G ( y, z) ⩽ l 2 ⩽ ∣ V( G)∣ − l 1 − 1. The augmented cube, proposed by Choudum and Sunitha [6] to be an enhancement of the n-cube Q n , not only retains some attractive characteristics of Q n but also possesses many distinguishing properties of which Q n lacks. In this paper, we investigate the panpositionable panconnectedness with respect to the class of augmented cubes. As a consequence, many topological properties related to cycle and path embedding in augmented cubes, such as pancyclicity, panconnectedness, and panpositionable Hamiltonicity, can be drawn from our results.