Almost Moore and the largest mixed graphs of diameters two and three

Abstract

Almost Moore mixed graphs appear in the context of the degree/diameter problem as a class of extremal mixed graphs, in the sense that their order is one unit less than the Moore bound for such graphs. The problem of their existence has been considered just for diameter 2. In this paper, we give a complete characterization of these extremal mixed graphs for diameters 2 and 3. We also derive some optimal constructions for other diameters.

This research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. The research of M. A. Fiol was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023.