Construction of extremal mixed graphs of diameter two

Identificador:  imarina:9440438

Handle: https://hdl.handle.net/20.500.11797/imarina9440438

Autors:  Lopez, Nacho; Perez-Roses, Hebert; Pujolas, Jordi; Zdimalova, Maria

Resum:
Graphs and digraphs with maximum order allowed by its degree and diameter have been widely studied in the context of the Degree/Diameter problem. This problem turns out to be very interesting in the mixed case, where many open problems arise, specially when the diameter is two and the order of the graph achieves the largest theoretical value given by the mixed Moore bound. These extremal graphs are known as mixed Moore graphs. In this paper we construct by voltage assignment some infinite families of mixed graphs of diameter two and order approaching the Moore bound. One of these families, in particular, yields most of the known mixed Moore graphs. We also present other families which are the result of the first known extension of the paradigmatic McKay-Miller-Sirafi construction (McKay et al., 1998). (C) 2018 Elsevier B.V. All rights reserved.