A family of mixed graphs with large order and diameter 2

作者：Araujo Pardo G^*; Balbuena C; Miller M; Zdimalova M

来源：Discrete Applied Mathematics, 2017, 218: 57-63.

DOI：10.1016/j.dam.2016.09.034

• Mixed Moore graphs
• Projective planes

A mixed regular graph is a connected simple graph in which each vertex has both a fixed outdegree (the same indegree) and a fixed undirected degree. A mixed regular graphs is said to be optimal if there is not a mixed regular graph with the same parameters and bigger order.
We present a construction that provides mixed graphs of undirected degree q, directed degree q-1/2 and order 2q(2), for q being an odd prime power. Since the Moore bound for a mixed graph with these parameters is equal to 9q(2)-4q+3/4 the defect of these mixed graphs is (q-2/2)(2)-1/4.
In particular we obtain a known mixed Moore graph of order 18, undirected degree 3 and directed degree 1 called Bosak's graph and a new mixed graph of order 50, undirected degree 5 and directed degree 2, which is proved to be optimal.

• 出版日期2017-2-19