Discrete Mathematics & Theoretical Computer Science (Jan 2006)
Some new optimal and suboptimal infinite families of undirected double-loop networks
Abstract
Let n, s be positive integers such that 2≤s<n and s≠ n / 2. An undirected double-loop network G(n; 1, s) is an undirected graph (V, E), where V = ℤ n = {0, 1, 2, …, n-1 } and E = { (i, i+1 mod n), (i, i+s mod n) | i ∈ℤ}. It is a circulant graph with n nodes and degree 4. In this paper, the sufficient and necessary conditions for a class of undirected double-loop networks to be optimal are presented. By these conditions, 6 new optimal and 5 new suboptimal infinite families of undirected double-loop networks are given.