Algebraic Constructions for the Digraph Degree-Diameter Problem

Nyumbu Chishwashwa, Vance Faber, Noah Streib

Published 2024-05-20Version 1

The degree-diameter problem for graphs is to find the largest number of vertices a graph can have given its diameter and maximum degree. We show we can realize this problem in terms of quasigroups, 1-factors and permutation groups. Our investigation originated from the study of graphs as the Cayley graphs of groupoids with d generators, a left identity and right cancellation; that is, a right quasigroup. This enables us to provide compact algebraic definitions for some important graphs that are either given as explicit edge lists or as the Cayley coset graphs of groups larger than the graph. One such example is a single expression for the Hoffman-Singleton graph. From there, we notice that the groupoids can be represented uniquely by a set of disjoint permutations and we explore the consequences of that observation.