Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Preprint
Data sources: ZENODO
addClaim

Improved lower bounds for the degree-diameter problem from metacyclic groups, coset graphs and affine lifts

Authors: Rajiv, Rishabh;

Improved lower bounds for the degree-diameter problem from metacyclic groups, coset graphs and affine lifts

Abstract

We present graphs that improve the best published lower bounds for the degree-diameter problem in eighteen parameter pairs $(d,k)$ with degree $d \le 20$ and diameter $k \le 10$. Fifteen of the graphs are Cayley graphs of semidirect products of two cyclic groups, given by explicit generating sets. One is a coset graph of a finite simple group: a $6$-regular graph of diameter $5$ on $1518$ vertices from $\mathrm{PSL}(2,23)$. The remaining two, of degree $20$ and diameters $3$ and $5$ on $2750$ and $450000$ vertices, come from a lift construction in which a small regular graph is blown up by fibres $F_q^{\,s}$ and each edge joins a fibre point to an affine line in the neighbouring fibre; the diameter-$5$ graph exceeds the previous bound by $59.7$ percent. Every graph is specified exactly, and the claimed degree and diameter of each are confirmed by independent breadth-first search, from every vertex when the graph carries no transitive symmetry. Complete descriptions, adjacency data and standalone verification scripts accompany the paper.

Powered by OpenAIRE graph
Found an issue? Give us feedback