Search

A double-loop digraph G=G(N;s1,s2), with gcd(N,s1,s2)=1, has the set of vertices V=ZN and the adjacencies are given by u→u+si (mod N) i=1,2. The diameter of G, denoted by D(N;s1,s2), is known to be lower bounded by lb(N) withThis lower bound is known to be sharp. For a fixed N∈N, some algorithms to find D(N) and steps 1⩽α<β such that D(N;α,β)=D(N) are known through the bibliography, being of numerical nature all of them.In this paper we propose a symbolic algorithm on the following problem: Given a number of vertices N0∈N, find if possible an infinite family of tight double-loop digraphs G(x)=G(N(x);s1(x),s2(x)) such that N(x0)=N0 and D(x)=D(N(x);s1(x),s2(x))=lb(N(x)) ∀x⩾x0. This family is parameterized by the integer x with N(x)∈Z and s1(x),s2(x)∈Z/(N(x)). As a direct consequence of such an explicit family of digraphs G(x), we also have an additive basis {s1(x),s2(x)} which covers the elements of Z/(N(x)) with optimal order.The time cost of this algorithm is O(√ of N0 log N0), in the worst case. [Copyright &y& Elsevier]