Large circulant graphs of fixed diameter and arbitrary degree

DOI10.26493/1855-3974.969.659zbMATH Open1380.05097arXiv1506.04962OpenAlexW1816839677WikidataQ129366259 ScholiaQ129366259MaRDI QIDQ4604515

No author found.

Publication date: 26 February 2018

Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)

Abstract: We consider the degree-diameter problem for undirected and directed circulant graphs. To date, attempts to generate families of large circulant graphs of arbitrary degree for a given diameter have concentrated mainly on the diameter 2 case. We present a direct product construction yielding improved bounds for small diameters and introduce a new general technique for "stitching" together circulant graphs which enables us to improve the current best known asymptotic orders for every diameter. As an application, we use our constructions in the directed case to obtain upper bounds on the minimum size of a subset $A$ of a cyclic group of order $n$ such that the $k$-fold sumset $kA$ is equal to the whole group. We also present a revised table of largest known circulant graphs of small degree and diameter.

Full work available at URL: https://arxiv.org/abs/1506.04962

zbMATH Keywords

Cayley graphssumsetscirculant graphsdegree-diameter problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Distance in graphs (05C12) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• Searching for large multi-loop networks
• Abelian Cayley graphs of given degree and diameter 2 and 3
• Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups
• Moore graphs and beyond: a survey of the degree/diameter problem
• Primes in arithmetic progressions

Related Items (8)

On the non-existence of Abelian Moore Cayley graphs with excess one ⋮ Some large graphs with given degree and diameter ⋮ Unnamed Item ⋮ Parallel optimization and performance tuning on a Kunpeng cluster of genetic algorithm for synthesis of circulant networks ⋮ Wide diameters of de Bruijn graphs ⋮ Unnamed Item ⋮ Large vertex symmetric digraphs ⋮ Unnamed Item

Recommendations

• Regular graphs of large girth and arbitrary degree 👍 👎
• Large Cayley digraphs of given degree and diameter 👍 👎
• Large graphs with given degree and diameter. II 👍 👎
• Large planar graphs with given diameter and maximum degree 👍 👎
• Maximal diameter on a class of circulant graphs 👍 👎
• Large Graphs with Given Degree and Diameter—Part I 👍 👎
• Large vertex-transitive and Cayley graphs with given degree and diameter 👍 👎
• Some large graphs with given degree and diameter 👍 👎
• Unnamed Item 👍 👎
• Unnamed Item 👍 👎

This page was built for publication: Large circulant graphs of fixed diameter and arbitrary degree