Geodesic pancyclicity of twisted cubes (Q424780): Difference between revisions

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. The \(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. The 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.