For a nonnegative integer \(k,\) a pair of vertices \(\langle u, v \rangle\) in a graph \(G\) is said to be geodesic \(k\)-pancyclic if every shortest path between \(u\) and \(v\) in \(G\) lies on a cycle of length \(l,\) where \(\max\{2d_G(u, v) + k, 3\} \leq l \leq n.\) A graph \(G\) is geodesic \(k\)-pancyclic if, for every two vertices \(u, v \in V(G)\), \(\langle u, v \rangle\) is geodesic \(k\)-pancyclic. Therefore, when studying shortest path related properties in such a graph \(G\), especially when used as an interconnection network, one can apply the related results and/or algorithms btained for the cycles.NEWLINENEWLINEThe \(n\)-dimensional twisted cube structure, denoted by \(TQ_n\), is one of many variants of the popular and well studied hypercube structure. The chief attraction of the twisted cubes is that, while having the same number of edges, its diameter is only half of that of the hypercube of the same dimension, thus cutting down the routing cost. Various topological properties of \(TQ_n\) such as matching properties, embedding properties, fault-tolerance properties, and surface areas, have appeared in literature [\textit{R. Bhaskar} et al., Congr. Numerantium 205, 175--185 (2010; Zbl 1231.05209); \textit{J. Fan, X. L. Lin} and \textit{X. H. Jia}, ``Optimal path embedding in crossed cubes, IEEE Trans. Parallel Distrib. Comput. 16, 1190--1200 (2005); ``Optimal path embeddings of paths with various lengths in twisted cubes, IEEE Trans. Parallel Distrib. Comput. 18, 511--521 (2007); \textit{J. Fan, S. Zhang, X. Jia} and \textit{G. Zhang}, ``A fault-free unicast algorithm in twisted cubes with the restricted faulty node set, in: Proceedings of the 15th international conference on parallel and distributed systems (ICPADS 2009). 316--323 (2009); \textit{W.-T. Huang} et al., J. Parallel Distrib. Comput. 62, No. 4, 591--604 (2002; Zbl 1008.68017); \textit{E. Cheng, K. Qiu} and \textit{Z. Shen}, Lect. Notes Comput. Sci. 6831, 411--423 (2011; Zbl 1342.68252); \textit{M. Yang} et al., Inf. Sci. 176, No. 6, 676--690 (2006; Zbl 1103.68028)]. It is worth pointing out that, unlike the majority of the interconnection networks, \(TQ_n\) is asymmetric [\textit{S. Abraham} and \textit{K. Padmanabhan}, ``The twisted cube topology for multiprocessor: a study in network asymmetry, J. Parallel Distrib. Comput. 13, 104--110 (1991)], which makes the related analysis more challenging, as demonstrated in this paper.NEWLINENEWLINEThe central result of this paper is that \(TQ_n\) is geodesic 2-pancyclic for each odd integer \(n \geq 3\), implying that every edge of \(TQ_n\) is included in at least one cycle of every length between 3 and \(n\). This technical result is obtained through a detailed analysis, exhausting all the possible scenarios. It is also shown that \(TQ_n \times K_2\) is geodesic 4-pancyclic.
- Geodesic pancyclicity and balanced pancyclicity of augmented cubes
- Algorithms and Computation
- scientific article; zbMATH DE number 3102984
- Embedding of cycles in twisted cubes with edge-pancyclic
- Panconnectivity of locally twisted cubes
- Edge-pancyclicity and Hamiltonian connectivity of twisted cubes
- Geodesic pancyclicity and balanced pancyclicity of the generalized base-\(b\) hypercube
- Cycle construction and geodesic cycles with application to the hypercube
- Geodesics in CAT(0) cubical complexes
- Edge-pancyclicity of Möbius cubes
- Advances on the Hamiltonian problem -- a survey
- Algorithms and Computation
- Complete path embeddings in crossed cubes
- Cycles in butterfly graphs
- Cycles in the cube-connected cycles graph
- Edge-pancyclicity and path-embeddability of bijective connection graphs
- Embedding of cycles in arrangement graphs
- Embedding of cycles in twisted cubes with edge-pancyclic
- Embedding paths and cycles in 3-ary \(n\)-cubes with faulty nodes and links
- Fault-tolerant Hamiltonicity of twisted cubes
- Geodesic pancyclicity and balanced pancyclicity of augmented cubes
- Geodesic-pancyclic graphs
- Graph theory
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- Linear array and ring embeddings in conditional faulty hypercubes
- Node-pancyclicity and edge-pancyclicity of hypercube variants
- On embedding cycles into faulty twisted cubes
- On the double-vertex-cycle-connectivity of crossed cubes
- On the path-connectivity, vertex-pancyclicity, and edge-pancyclicity of crossed cubes
- Path embeddings in faulty 3-ary \(n\)-cubes
- Survey on path and cycle embedding in some networks
- The m-pancycle-connectivity of a WK-recursive network
- Topological properties of twisted cube
- Geodesic pancyclicity and balanced pancyclicity of the generalized base-\(b\) hypercube
- scientific article; zbMATH DE number 1766866 (Why is no real title available?)
- scientific article; zbMATH DE number 6940807 (Why is no real title available?)
- Hamiltonian properties of honeycomb meshes
- A parallel algorithm for constructing independent spanning trees in twisted cubes
- Algorithms and Computation
- Geodesic pancyclicity and balanced pancyclicity of augmented cubes
- Complete binary trees embeddings in Möbius cubes
- Embedding of cycles in twisted cubes with edge-pancyclic
This page was built for publication: Geodesic pancyclicity of twisted cubes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q424780)
