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

zbMATH Open1305.05107arXiv1404.3948MaRDI QIDQ490264FDOQ490264

Robert R. Lewis

Publication date: 22 January 2015

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

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.

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

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)

Cites Work

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

Cited In (10)

• Searching for large multi-loop networks
• Greedy routing in circulant networks
• Efficient eight-regular circulants based on the Kronecker product
• The degree-diameter problem for circulant graphs of degrees 10 and 11
• Parallel optimization and performance tuning on a Kunpeng cluster of genetic algorithm for synthesis of circulant networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the non-existence of Abelian Moore Cayley graphs with excess one
• NEW FAMILIES OF MULTIPLICATIVE CIRCULANT NETWORKS
• Title not available (Why is that?)

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)