Algebraic Constructions for the Digraph Degree-Diameter Problem

Autor:	Chishwashwa, Nyumbu, Faber, Vance, Streib, Noah
Rok vydání:	2024
Předmět:	Mathematics - Combinatorics Mathematics - Group Theory 05C20 (Primary) 05C25 05C38 05C90 (Secondary)
Druh dokumentu:	Working Paper
Popis:	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. Comment: 24 pages05C20. arXiv admin note: text overlap with arXiv:2208.10537
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2405.12374 Zobrazit plný text záznamu View this record from Arxiv