The unique mixed almost moore graph with parameters k = 2, r = 2 and z = 1

Abstract

A natural upper bound for the maximum number of vertices in a mixed graph with maximum undirected degree r, maximum directed out-degree z and diameter k is given by the mixed Moore bound. Graphs with order attaining the Moore bound are known as Moore graphs, and they are very rare. Besides, graphs with prescribed parameters and order one less than the corresponding Moore bound are known as almost Moore graphs. In this paper we prove that there is a unique mixed almost Moore graph of diameter k = 2 and parameters r = 2 and z = 1.

To our beloved friend Mirka Miller. She would love to see this result concerning mixed Moore graphs. Research of Nacho López and Josep M. Miret was supported in part by grants MTM2013-46949-P (Spanish Ministerio de Economa y Competitividad) and 2014SGR-1666 (Generalitat de Catalunya).