2018/06/11 by F. Aguiló-Gost, Aguiló, F., Marisa Zaragozá +1
Computer Science · #05012 #05C25 #Advanced Graph Theory Research #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1806.03899
openalex publication_date 2018/06/11 · openalex created_date 2018/06/13 · openalex updated_date 2026/07/28
Let Γ=Cay(G,T) be a Cayley digraph over a finite Abelian group G with respect the generating set T\not\ni0. Γ has order ord(Γ)=|G|=n and degree deg(Γ)=|T|=d. Let k(Γ) be the diameter of Γ and denote κ(d,n)=min\k(Γ):~\textrmord(Γ)=n,\textrmdeg(Γ)=d\. We give a closed expression, ℓ(d,n), of a tight lower bound of κ(d,n) by using the so called \em solid density introduced by Fiduccia, Forcade and Zito. A digraph Γ of degree d is called \em tight when k(Γ)=κ(d,|Γ|)=ℓ(d,|Γ|) 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 \Γi\i=1^\textrmc(Γ) from a given tight digraph Γ. Moreover, we find a closed expression of the cardinality c(Γ) of this sequence. It is perhaps surprising that c(Γ) depends only on n and d and not on the structure of Γ.