The Degree-Diameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case
From MaRDI portal
Publication:4652604
DOI10.1137/S0895480100372899zbMath1056.05046arXivmath/9412223MaRDI QIDQ4652604
Vance Faber, Randall Dougherty
Publication date: 28 February 2005
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Abstract: We address the degree-diameter problem for Cayley graphs of Abelian groups (Abelian graphs), both directed and undirected. The problem turns out to be closely related to the problem of finding efficient lattice coverings of Euclidean space by shapes such as octahedra and tetrahedra; we exploit this relationship in both directions. In particular, we find the largest Abelian graphs with 2 generators (dimensions) and a given diameter. (The results for 2 generators are not new; they are given in the literature of distributed loop networks.) We find an undirected Abelian graph with 3 generators and a given diameter which we conjecture to be as large as possible; for the directed case, we obtain partial results, which lead to unusual lattice coverings of 3-space. We discuss the asymptotic behavior of the problem for large numbers of generators. The graphs obtained here are substantially better than traditional toroidal meshes, but, in the simpler undirected cases, retain certain desirable features such as good routing algorithms, easy constructibility, and the ability to host mesh-connected numerical algorithms without any increase in communication times.
Full work available at URL: https://arxiv.org/abs/math/9412223
Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Distance in graphs (05C12)
Related Items (40)
Greedy routing in circulant networks ⋮ Abelian Cayley digraphs with asymptotically large order for any given degree ⋮ Searching for large multi-loop networks ⋮ On the non-existence of Abelian Moore Cayley graphs with excess one ⋮ A SURVEY ON UNDIRECTED CIRCULANT GRAPHS ⋮ The degree/diameter problem for mixed abelian Cayley graphs ⋮ The Dilating Method for Cayley digraphs on finite Abelian groups ⋮ Lower Bounds on Lattice Covering Densities of Simplices ⋮ New Moore-like bounds and some optimal families of abelian Cayley mixed graphs ⋮ Distances to lattice points in knapsack polyhedra ⋮ Improved lower bounds on the degree-diameter problem ⋮ On the nonexistence of lattice tilings of \(\mathbb{Z}^n\) by Lee spheres ⋮ On abelian Cayley graphs of diameter two and defect one ⋮ Unnamed Item ⋮ The maximum degree and diameter-bounded subgraph in the mesh ⋮ Diameters of random circulant graphs ⋮ Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups ⋮ Large Cayley digraphs of given degree and diameter ⋮ Abelian Cayley graphs of given degree and diameter 2 and 3 ⋮ The degree-diameter problem for circulant graphs of degree 8 and 9 ⋮ NEW FAMILIES OF MULTIPLICATIVE CIRCULANT NETWORKS ⋮ On lattice coverings by simplices ⋮ A Moore-like bound for mixed abelian Cayley graphs ⋮ A geometric approach to dense Cayley digraphs of finite abelian groups ⋮ Efficient eight-regular circulants based on the Kronecker product ⋮ Unnamed Item ⋮ Some new large (Δ, 3)‐graphs ⋮ Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter ⋮ Lower bound on the translative covering density of octahedra ⋮ On the lattice programming gap of the group problems ⋮ The degree-diameter problem for circulant graphs of degrees 10 and 11 ⋮ On the packing density of Lee spheres ⋮ No lattice tiling of \(\mathbb{Z}^n\) by Lee sphere of radius 2 ⋮ Graphs of given degree and diameter obtained as abelian lifts of dipoles ⋮ Circulant graphs and tessellations on flat tori ⋮ Unnamed Item ⋮ An improved Moore bound and some new optimal families of mixed abelian Cayley graphs ⋮ Unnamed Item ⋮ A note on large Cayley graphs of diameter two and given degree ⋮ Cayley Graphs of Diameter Two from Difference Sets
This page was built for publication: The Degree-Diameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case
