×

Vertex-bipancyclicity of the generalized honeycomb tori. (English) Zbl 1165.05323

Summary: Assume that \(m,n\) and \(s\) are integers with \(m\geq 2,n\geq 4,0\leq s<n\) and \(s\) is of the same parity of \(m\). The generalized honeycomb tori \(\text{GHT}(m,n,s)\) have been recognized as an attractive architecture to existing torus interconnection networks in parallel and distributed applications. A bipartite graph \(G\) is bipancyclic if it contains a cycle of every even length from 4 to |\(V(G)\)| inclusive. \(G\) is vertex-bipancyclic if for any vertex \(v\in V(G)\), there exists a cycle of every even length from 4 to |\(V(G)\)| that passes \(v\). A bipartite graph \(G\) is called \(k\)-vertex-bipancyclic if every vertex lies on a cycle of every even length from \(k\) to |\(V(G)\)|. In this article, we prove that \(\text{GHT}(m,n,s)\) is 6-bipancyclic, and is bipancyclic for some special cases. Since \(\text{GHT}(m,n,s)\) is vertex-transitive, the result implies that any vertex of \(\text{GHT}(m,n,s)\) lies on a cycle of length \(l\), where \(l\geq 6\) and is even. Besides, \(\text{GHT}(m,n,s)\) is vertex-bipancyclic in some special cases. The result is optimal in the sense that the absence of cycles of certain lengths on some \(\text{GHT}(m,n,s)\)’s is inevitable due to their hexagonal structure.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI

References:

[1] Parhami, B., Introduction to Parallel Processing: Algorithms and Architectures (1999), Plenum Press: Plenum Press New York
[2] Stojmenovic, I., Honeycomb networks: Topological properties and communication algorithms, IEEE Transactions on Parallel and Distributed Systems, 8, 1036-1042 (1997)
[3] Carle, J.; Myoupo, J.-F.; Seme, D., All-to-all broadcasting algorithms on honeycomb networks and applications, Parallel Processing Letters, 9, 539-550 (1999)
[4] Megson, G. M.; Yang, X.; Liu, X., Honeycomb tori are hamiltonian, Information Processing Letters, 72, 99-103 (1999) · Zbl 0999.68010
[5] Megson, G. M.; Liu, X.; Yang, X., Fault-tolerant ring embedding in a honeycomb torus with nodes failures, Parallel Processing Letters, 9, 551-561 (1999)
[6] Parhami, B.; Kwai, D. M., A unified formulation of honeycomb and diamond networks, IEEE Transactions on Parallel and Distributed Systems, 12, 74-80 (2001)
[7] Cho, H.; Hsu, L., Generalized honeycomb torus, Information Processing Letters, 86, 185-190 (2003) · Zbl 1162.68739
[8] Xiao, W.; Parhami, B., Further mathematical properties of Cayley digraphs applied to hexagonal and honeycomb meshes, Discrete Applied Mathematics, 155, 1752-1760 (2007) · Zbl 1127.68072
[9] Manuel, P.; Rajan, B.; Rajasingh, I.; M, C. M., On minimum metric dimension of honeycomb networks, Journal of Discrete Algorithms, 6, 20-27 (2008) · Zbl 1159.05308
[10] Yang, X.; Tang, Y.-Y.; Lu, Q.; He, Z., Optimal doublecast path in hexagonal honeycomb mesh, Applied Mathematics and Computation, 182, 267-1279 (2006) · Zbl 1161.68368
[11] Teng, Y.-H.; Tan, Jimmy J. M.; Hsu, L.-H., The globally Bi-3*-connected property of the honeycomb rectangular torus, Information Sciences, 177, 5573-5589 (2007) · Zbl 1132.68047
[12] Carle, J.; Myoupo, J.-F.; Stojmenovic, I., Higher dimensional honeycomb networks, Journal of Interconnection Networks, 2, 391-420 (2001)
[13] Yang, X.; Evans, D. J.; Lai, H.; Megson, G. M., Generalized honeycomb torus is hamiltonian, Information Processing Letters, 92, 31-37 (2004) · Zbl 1173.68426
[14] Xu, J.-M., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, London, pp. 18-22 · Zbl 1046.68026
[15] Araki, T., Edge-pancyclicity of recursive circulants, Information Processing Letters, 88, 287-292 (2003) · Zbl 1178.68022
[16] Hu, Ken S.; Yeoh, S.-S.; Chen, C.-Y.; Hsu, L.-H., Node-pancyclicity and edge-pancyclicity of hypercube variants, Information Processing Letters, 102, 1-7 (2007) · Zbl 1185.05089
[17] Xu, M.; Hu, X.-D.; Zhu, Q., Edge-bipancyclicity of star graphs under edge-fault tolerant, Applied Mathematics and Computation, 183, 972-979 (2006) · Zbl 1109.05059
[18] Yang, M.-C.; Tan, Jimmy J. M.; Hsu, L.-H., Highly fault-tolerant cycle embeddings of hypercubes, Journal of Systems Architecture, 53, 227-232 (2007)
[19] Chang, C.-P.; Wang, J.-N.; Hsu, L.-H., Topological properties of twisted cube, Information Sciences, 113, 147-167 (1999) · Zbl 0952.68008
[20] Germa, A.; Heydemann, M.-C.; Sotteau, D., Cycles in the cube-connected cycle graph, Discrete Applied Mathematics, 83, 135-155 (1998) · Zbl 0910.05037
[21] Goddard, W.; Henning, M. A., Pancyclicity of the prism, Discrete Mathematics, 234, 139-142 (2001) · Zbl 1112.05313
[22] Jha, P. K., Kronecker products of paths and cycles: Decomposition, factorization and bi-pancyclicity, Discrete Mathematics, 182, 153-167 (1998) · Zbl 0890.05052
[23] Ramachandran, S.; Parvathy, R., Pancyclicity and extendability in strong products, Journal of Graph Theory, 22, 1, 75-82 (1996) · Zbl 0851.05070
[24] Chen, G.-H.; Fu, J.-S.; Fang, J.-F., Hypercomplete: A pancyclic recursive topology for large-scale distributed multicomputer systems, Networks, 35, 1, 56-69 (2000) · Zbl 0938.90066
[25] Hwang, S.-C.; Chen, G.-H., Cycles in butterfly graphs, Networks, 35, 2, 161-171 (2000) · Zbl 0957.90016
[26] Alspach, B.; Hare, D., Edge-pancyclic block-intersection graphs, Discrete Mathematics, 97, 17-24 (1991) · Zbl 0758.05010
[27] Bang-Jansen, J.; Guo, Y., A note on vertex pancyclic oriented graphs, Journal of Graph Theory, 31, 313-318 (1999) · Zbl 0944.05061
[28] Lih, K.-W.; Zengmin, S.; Weifan, W.; Kemin, Z., Edge-pancyclicity of coupled graphs, Discrete Applied Mathematics, 119, 259-264 (2002) · Zbl 1068.05037
[29] Randerath, B.; Schiermeyer, I.; Tewes, M.; Volkmann, L., Vertex pancyclic graphs, Discrete Applied Mathematics, 120, 219-237 (2002) · Zbl 1001.05070
[30] Hsieh, S.-Y.; Shiu, J.-Y., Cycle embedding of augmented cubes, Applied Mathematics and Computation, 191, 314-319 (2007) · Zbl 1193.05098
[31] Xu, M.; Hu, X.-D.; Xu, J.-M., Edge-pancyclicity and hamiltonian laceability of the balanced hypercubes, Applied Mathematics and Computation, 189, 1393-1401 (2007) · Zbl 1161.94012
[32] Chang, J.-M.; Yang, J.-S., Fault-tolerant cycle-embedding in alternating group graphs, Applied Mathematics and Computation, 197, 760-767 (2008) · Zbl 1148.05049
[33] Ma, M.; Liu, G.; Xu, J.-M., Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes, Parallel Computing, 33, 36-42 (2007)
[34] Park, J.-H., Panconnectivity and edge-pancyclicity of faulty recursive circulant \(g(2^m, 4)\), Theoretical Computer Science, 390, 70-80 (2008) · Zbl 1134.68044
[35] Huang, C.-H.; Fang, J.-F., The pancyclicity and the hamiltonian-connectivity of the generalized base-\(b\) hypercube, Computers and Electrical Engineering, 34, 263-269 (2008) · Zbl 1147.68416
[36] Chena, Y.-Y.; Duh, D.-R.; Yea, T.-L.; Fu, J.-S., Weak-vertex-pancyclicity of \((n, k)\)-star graphs, Theoretical Computer Science, 396, 191-199 (2008) · Zbl 1140.68051
[37] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1980), North-Holland: North-Holland New York · Zbl 1134.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.