The degree-diameter problem for circulant graphs of degree 8 and 9

MaRDI QIDQ490264zbMATH OpenFDO

Authors Robert R. Lewis

Publication date 22 January 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.3948, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p50

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

circulant graphsextremalabelian Cayley graphsdegree-diameter

Mathematics Subject Classification ID

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

Abstract: This paper considers the degree-diameter problem for undirected circulant graphs. The focus is on extremal graphs of given (small) degree and arbitrary diameter. The published literature only covers graphs of up to degree 7. The approach used to establish the results for degree 6 and 7 has been extended successfully to degree 8 and 9. Candidate graphs are defined as functions of the diameter for both degree 8 and degree 9. They are proven to be extremal for small diameters. They establish new lower bounds for all greater diameters, and are conjectured to be extremal. The existence of the degree 8 solution is proved for all diameters. Finally some conjectures are made about solutions for circulant graphs of higher degree.

Recommendations

• The degree-diameter problem for circulant graphs of degrees 10 and 11
• Large circulant graphs of fixed diameter and arbitrary degree
• On an extremal family of circulant networks
• Series of families of degree six circulant graphs
• Moore graphs and beyond: a survey of the degree/diameter problem

Cites work

• Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups
• Note on a “Square” Functional Equation
• Perfect Codes in the Lee Metric and the Packing of Polyominoes
• The Degree-Diameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case
• Tilings in Lee metric
• Undirected loop networks

Cited in

(10)

• scientific article; zbMATH DE number 7310263 (Why is no real title available?)
• Parallel optimization and performance tuning on a Kunpeng cluster of genetic algorithm for synthesis of circulant networks
• On the non-existence of Abelian Moore Cayley graphs with excess one
• Searching for large multi-loop networks
• scientific article; zbMATH DE number 7656036 (Why is no real title available?)
• The degree-diameter problem for circulant graphs of degrees 10 and 11
• Greedy routing in circulant networks
• Series of families of degree six circulant graphs
• Efficient eight-regular circulants based on the Kronecker product
• New families of multiplicative circulant networks

This page was built for publication: The degree-diameter problem for circulant graphs of degree 8 and 9

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