Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes

✍ Scribed by Meijie Ma; Guizhen Liu; Jun-Ming Xu

• Publisher: Elsevier Science
• Year: 2007
• Tongue: English
• Weight: 312 KB
• Volume: 33
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/j.parco.2006.11.008

✦ Synopsis

As an enhancement on the hypercube Q n , the augmented cube AQ n , proposed by Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks, 40(2) (2002), 71-84], not only retains some of the favorable properties of Q n but also possesses some embedding properties that Q n does not. For example, AQ n contains cycles of all lengths from 3 to 2 n , but Q n contains only even cycles. In this paper, we obtain two stronger results by proving that AQ n contains paths, between any two distinct vertices, of all lengths from their distance to 2 n À 1; and AQ n still contains cycles of all lengths from 3 to 2 n when any (2n À 3) edges are removed from AQ n . The latter is optimal since AQ n is (2n À 1)regular.