Cycles in the cube-connected cycles graph
The cube-connected cycles graph, denoted \(\text{CCC}_n\), is the graph of order \(n2^n\) whose vertices are labeled \((\ell, x)\), where \(\ell\) is an integer between 0 and \(n-1\) which is called the level of the vertex, and \(x\) is a binary string of length \(n\) called the row of \(x\). Vertices \((\ell, x)\) and \((\ell', y)\) are adjacent in \(\text{CCC}_n\) if and only if either \(x=y\) and \(| \ell - \ell'| = 1\) or \(\ell = \ell'\) and \(y = x(\ell)\). The graph \(\text{CCC}_n\) is derived from the \(n\)-dimensional hypercube by replacing each of its vertices by a cycle of length \(n\). The authors show that if \(n\) is odd, then \(\text{CCC}_n\) is close to being pancyclic, and if \(n\) is even, then \(\text{CCC}_n\) is close to being bi-pancyclic. In particular, they show the following: \(\text{CCC}_3\) contains cycles of length 3 and all lengths between 8 and 24; \(\text{CCC}_4\) contains cycles of length 4 and all even lengths between 8 and 64; for \(n \geq 5\), \(\text{CCC}_n\) contains cycles of length \(n\) and of every even length between 8 and \(n2^n\) except 10 and possibly \(n2^n - 2\); and if \(n\) is odd, \(\text{CCC}_n\) contains cycles of every odd length between \(n+6\) and \(n2^n - n - 2\) and also cycles of length \(n2^n - n + 2\).
scientific article; zbMATH DE number 1180306