Directed Moore hypergraphs Original Research Article

For graphs with maximum degree Δ and diameter D, an upper bound on the number of vertices is 1 + Δ∑d − 1i = 0(Δ − 1)i. This bound is called the Moore bound for graphs and the graphs that attain it are called Moore graphs. Similar bounds for directed graphs and for hypergraphs have been defined and the existence of directed Moore graphs and of Moore hypergraphs has been studied. In this article, we define a Moore bound for directed hypergraphs and show that directed Moore hypergraphs either are directed cycles, or have diameter one. Any directed hypergraph may be regarded as a factorization of a square nonnegative integer matrix into a pair of (0, 1)-matrices. In particular, the directed Moore hypergraphs of diameter 1 that have n vertices and m hyperarcs can be identified with factorizations J − I = XY where J is the n × n all-ones matrix, I is the n × n identity matrix, X is an n × m (0,1)-matrix, Y is an m × n (0, 1)-matrix, and X and Y have constant row sums. We conclude with a survey of results on factorizations of J − I.