Geodesic pancyclicity and balanced pancyclicity of Augmented cubes |
| |
Authors: | Hong-Chun Hsu Pao-Lien Lai |
| |
Affiliation: | a Department of Medical Informatics, Tzu Chi University, Hualien, Taiwan 970, ROC b Department of Computer Science and Information Engineering, National Dong Hwa University, Shoufeng, Hualien, Taiwan 97401, ROC c Department of Computer and Information Science, National Hualien University of Education, Hualien, Taiwan 970, ROC |
| |
Abstract: | For two distinct vertices u,v∈V(G), a cycle is called geodesic cycle with u and v if a shortest path of G joining u and v lies on the cycle; and a cycle C is called balanced cycle with u and v if dC(u,v)=max{dC(x,y)|x,y∈V(C)}. A graph G is pancyclic [J. Mitchem, E. Schmeichel, Pancyclic and bipancyclic graphs a survey, Graphs and applications (1982) 271-278] if it contains a cycle of every length from 3 to |V(G)| inclusive. A graph G is called geodesic pancyclic [H.C. Chan, J.M. Chang, Y.L. Wang, S.J. Horng, Geodesic-pancyclic graphs, in: Proceedings of the 23rd Workshop on Combinatorial Mathematics and Computation Theory, 2006, pp. 181-187] (respectively, balanced pancyclic) if for each pair of vertices u,v∈V(G), it contains a geodesic cycle (respectively, balanced cycle) of every integer length of l satisfying max{2dG(u,v),3}?l?|V(G)|. Lai et al. [P.L. Lai, J.W. Hsue, J.J.M. Tan, L.H. Hsu, On the panconnected properties of the Augmented cubes, in: Proceedings of the 2004 International Computer Symposium, 2004, pp. 1249-1251] proved that the n-dimensional Augmented cube, AQn, is pancyclic in the sense that a cycle of length l exists, 3?l?|V(AQn)|. In this paper, we study two new pancyclic properties and show that AQn is geodesic pancyclic and balanced pancyclic for n?2. |
| |
Keywords: | Augmented cubes Panconnected Pancyclic Geodesic pancyclic Balanced pancyclic Interconnection networks |
本文献已被 ScienceDirect 等数据库收录! |
|