The degree-diameter problem for circulant graphs of degrees 10 and 11

DOI10.1016/J.DISC.2018.05.024zbMATH Open1392.05027arXiv1803.07071OpenAlexW2809906755WikidataQ129617180 ScholiaQ129617180MaRDI QIDQ724874FDOQ724874

Authors: Robert R. Lewis 

Publication date: 26 July 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: This paper considers the degree-diameter problem for undirected circulant graphs. For degrees 10 and 11 newly discovered families of circulant graphs of arbitrary diameter are presented which are largest known and are conjectured to be extremal. They are also the largest-known Abelian Cayley graphs of these degrees. For each such family the order of every graph in the family is defined by a quintic polynomial function of the diameter which is specific to the family. The elements of the generating set for each graph are similarly defined by a set of polynomials in the diameter. The existence of the graphs in the degree 10 families has been proved for all diameters. These graphs are consistent with a conjecture on the order of extremal Abelian Cayley and circulant graphs of any degree and diameter. This is the extended version of the paper, including the proof steps for degree 10 graphs covering all diameter classes and an appendix listing additional tables of generating sets.

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

Recommendations

• The degree-diameter problem for circulant graphs of degree 8 and 9
• Series of families of degree six circulant graphs
• Large circulant graphs of fixed diameter and arbitrary degree
• On an extremal family of circulant networks
• Large Cayley digraphs of given degree and diameter

zbMATH Keywords

circulant graphextremal graphabelian Cayley graphdegree diameter

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07)

Cites Work

• A Combinatorial Problem Related to Multimodule Memory Organizations
• The Degree-Diameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case
• The degree-diameter problem for circulant graphs of degree 8 and 9
• Note on a “Square” Functional Equation
• Undirected loop networks
• Title not available (Why is that?)
• The degree-diameter problem for circulant graphs of degrees 10 and 11

Cited In (7)

• Series of families of degree six circulant graphs
• The degree-diameter problem for circulant graphs of degree 8 and 9
• Greedy routing in circulant networks
• 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?)
• On the non-existence of Abelian Moore Cayley graphs with excess one

This page was built for publication: The degree-diameter problem for circulant graphs of degrees 10 and 11

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