Cycles in the cube-connected cycles graph
type: Item
instance of: scholarly article
title: Cycles in the cube-connected cycles graph
zbMATH Open document ID: 0910.05037
DOI: 10.1016/S0166-218X(98)80001-2
author: Anne Germa
author: Marie-Claude Heydemann
author: D. Sotteau
published in: Discrete Applied Mathematics
publication date: 1998-10-08T00:00:00Z
full work available at URL: dam
review text: 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\).
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1180306
zbMATH Keywords: pancyclic
zbMATH Keywords: bi-pancyclic
zbMATH Keywords: cube-connected cycles graph
zbMATH Keywords: hypercube
reviewed by: Michael Raines
MaRDI profile type: Publication
cites work: Group Action Graphs and Parallel Architectures
cites work: Q3941433
cites work: Q4087221
cites work: Spanners of Hypercube-Derived Networks
cites work: On Hamiltonian cycles in Cayley graphs of wreath products
description: scientific article; zbMATH DE number 1180306