On solid density of Cayley digraphs on finite Abelian groups

F. Aguiló, M. Zaragozá

Published 2018-06-11Version 1

Let $\Gamma=$Cay$(G,T)$ be a Cayley digraph over a finite Abelian group $G$ with respect the generating set $T\not\ni0$. $\Gamma$ has order ord$(\Gamma)=|G|=n$ and degree deg$(\Gamma)=|T|=d$. Let $k(\Gamma)$ be the diameter of $\Gamma$ and denote $\kappa(d,n)=\min\{k(\Gamma):~\textrm{ord}(\Gamma)=n,\textrm{deg}(\Gamma)=d\}$. We give a closed expression, $\ell(d,n)$, of a tight lower bound of $\kappa(d,n)$ by using the so called {\em solid density} introduced by Fiduccia, Forcade and Zito. A digraph $\Gamma$ of degree $d$ is called {\em tight} when $k(\Gamma)=\kappa(d,|\Gamma|)=\ell(d,|\Gamma|)$ holds. Recently, the {\em Dilating Method} has been developed to derive a sequence of digraphs of constant solid density. In this work, we use this method to derive a sequence of tight digraphs $\{\Gamma_i\}_{i=1}^{\textrm{c}(\Gamma)}$ from a given tight digraph $\Gamma$. Moreover, we find a closed expression of the cardinality c$(\Gamma)$ of this sequence. It is perhaps surprising that c$(\Gamma)$ depends only on $n$ and $d$ and not on the structure of $\Gamma$.