Large circulant graphs of fixed diameter and arbitrary degree

DOI10.26493/1855-3974.969.659MaRDI QIDQ4604515zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 26 February 2018

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

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

zbMATH Keywords

Cayley graphscirculant graphsdegree-diameter problemsumsets

Mathematics Subject Classification ID

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

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.

Recommendations

• Large Graphs with Given Degree and Diameter—Part I
• Some large graphs with given degree and diameter
• Large graphs with given degree and diameter. II
• Large Cayley digraphs of given degree and diameter
• Maximal diameter on a class of circulant graphs
• scientific article; zbMATH DE number 861410
• scientific article; zbMATH DE number 784887
• Regular graphs of large girth and arbitrary degree
• Large vertex-transitive and Cayley graphs with given degree and diameter
• Large planar graphs with given diameter and maximum degree

Cites work

• 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
• Primes of prescribed congruence class in short intervals
• Searching for large multi-loop networks

Cited in

(15)

• Greedy routing in circulant networks
• Wide diameters of de Bruijn graphs
• A class of nearly optimal circulant graphs: \(\{c_p(m,m+1,p/\alpha)\}\)
• On the diameter of integral circulant graphs.
• scientific article; zbMATH DE number 3891413 (Why is no real title available?)
• The largest Laplacian and adjacency indices of complete caterpillars of fixed diameter
• Some large graphs with given degree and diameter
• scientific article; zbMATH DE number 147621 (Why is no real title available?)
• The degree-diameter problem for circulant graphs of degree 8 and 9
• On the non-existence of Abelian Moore Cayley graphs with excess one
• A new attainable lower bound for the number of nodes in quadruple circulant networks
• Large vertex symmetric digraphs
• Parallel optimization and performance tuning on a Kunpeng cluster of genetic algorithm for synthesis of circulant networks
• The degree-diameter problem for circulant graphs of degrees 10 and 11
• Large graphs with given degree and diameter. II

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604515)