Premium
Panconnectivity, fault‐tolerant hamiltonicity and hamiltonian‐connectivity in alternating group graphs
Author(s) -
Chang JouMing,
Yang JinnShyong,
Wang YueLi,
Cheng Yuwen
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20039
Subject(s) - combinatorics , mathematics , discrete mathematics , pancyclic graph , hamiltonian path , vertex (graph theory) , graph , topology (electrical circuits) , line graph , pathwidth
Abstract Jwo et al. [Networks 23 (1993) 315–326] introduced the alternating group graph as an interconnection network topology for computing systems. They showed that the proposed structure has many advantages over n ‐cubes and star graphs. For example, all alternating group graphs are hamiltonian‐connected (i.e., every pair of vertices in the graph are connected by a hamiltonian path) and pancyclic (i.e., the graph can embed cycles with arbitrary length with dilation 1). In this article, we give a stronger result: all alternating group graphs are panconnected, that is, every two vertices x and y in the graph are connected by a path of length k for each k satisfying d ( x , y ) ≤ k ≤ | V | − 1, where d ( x , y ) denotes the distance between x and y , and | V | is the number of vertices in the graph. Moreover, we show that the r ‐dimensional alternating group graph AG r , r ≥ 4, is ( r − 3)‐vertex fault‐tolerant Hamiltonian‐connected and ( r − 2)‐vertex fault‐tolerant hamiltonian. The latter result can be viewed as complementary to the recent work of Lo and Chen [IEEE Trans. Parallel and Distributed Systems 12 (2001) 209–222], which studies the fault‐tolerant hamiltonicity in faulty arrangement graphs. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 302–310 2004