Geodesic pancyclicity and balanced pancyclicity of the generalized base-b b hypercube
Recently, Chan etal. introduced geodesic-pancyclic graphs [H.C. Chan, J.M. Chang, Y.L.Wang, S.J. Horng, Geodesic-pancyclic graphs, Discrete Applied Mathematics 155 (15) (2007) 19711978] and weakly geodesic pancyclicity [H.C. Chan, J.M. Chang, Y.L.Wang, S.J. Horng, Geodesic-pancyclicity and fault-tolerant panconnectivity of augmented cubes, Applied Mathematics and Computation 207 (2009) 333339]. Hsu etal. proposed a new cycle-embedding property called balanced pancyclicity [H.C. Hsu, P.L. Lai, C.H.Tsai, Geodesic pancyclicity and balanced pancyclicity of augmented cubes, Information Processing Letters 101 (2007) 227232]. For a graph G(V,E) G ( V , E ) and any two vertices x x and y y of V V , a cycle R R containing x x and y y can be divided into two paths, Pt1 P t 1 and Pt2 P t 2 , joining x x and y y such that len ( P t 1 ) ? len ( P t 2 ) , where len ( ? ) denotes the length of the path ? ? . A geodesic cycle contains Pt1 P t 1 , which is the shortest path joining x x and y y in G G , whereas, in a balanced cycle of an even (respectively, odd) length, len ( P t 1 ) = len ( P t 2 ) (respectively, len ( P t 1 ) = len ( P t 2 ) ? 1 ). A graph is weakly geodesic pancyclic (respectively, balanced pancyclic) if every two vertices x x and y y are contained in a geodesic cycle (respectively, balanced cycle) from Max ( 3 , 2 Dist ( x , y ) ) to N N , where N N is the order of the graph. The interconnection network considered in this paper is the generalized base-b b hypercube, which is an attractive variant of the well-known hypercube. In fact, the generalized base-b b hypercube is the Cartesian product of complete graphs with b b vertices. The generalized base-b b hypercube is superior to the hypercube in many criteria, such as diameter, connectivity, and fault diameter. In this paper, we study weakly geodesic pancyclicity and balanced pancyclicity of the generalized base-b b hypercube. We show that the generalized base-b b hypercube is weakly geodesic pancyclic for b?3 b ? 3 and balanced pancyclic for b?4 b ? 4 .
balanced pancyclicity weakly geodesic pancyclicity interconnection networks generalized base-b b hypercubes b b b b b