The Degree Diameter Problem for General Mixed Graphs
From Combinatorics Wiki
The degree/diameter problem for general mixed graphs can be stated as follows:
Given three natural numbers , and , find the largest possible number of vertices in a mixed graph of maximum undirected degree , maximum directed out-degree and diameter .
In attempting to settle the values of , research activities in this problem have follow the following two directions:
- Increasing the lower bounds for by constructing ever larger mixed graphs.
- Lowering and/or setting upper bounds for by proving the non-existence of mixed graphs
whose order is close to the Moore bound , where , , , and .
Mixed Moore graphs
Mixed graphs of order with maximum undirected degree , maximum directed out-degree and diameter are called mixed Moore graphs. Such extremal mixed graphs are totally regular of degree and they have the property that for any ordered pair of vertices there is a unique trail from to of length at most the (finite) diameter . It is proved that mixed Moore graphs may only exist for diameter . In this case, Bosák gives the following necessary condition for their existence:
Let be a (proper) mixed Moore graph of diameter 2. Then, is totally regular with directed degree and undirected degree . Moreover, there must exist a positive odd integer such that and .
As a consequence, these extremal graphs may only exist for some (infinitely many) values of the order . Nevertheless, the existence of these graphs have been proved only for a 'few' cases. The unique infinite family of mixed Moore graphs known is the Kautz digraphs , for every and (where every digon has been identified by an edge). Gimbert proved that Kautz digraphs are the unique mixed Moore graphs with those parameters. An interesting proper mixed Moore graph of order 18 was given by Bosák (and its uniqueness was proved later by Nguyen et al.).
Jorgensen found two non-isomorphic proper mixed Moore graphs of order 108 of Cayley type. Recently, López et al. prove the non existence of mixed Moore graphs of orders 40, 54 and 84, translating the existence of the adjacency matrix of these mixed graphs through the Boolean satisfiability problem. Besides, there are many pairs satisfying Bosák necessary condition for which the existence of a proper mixed Moore graph was not yet known until now: