Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651159 | Discrete Mathematics | 2007 | 7 Pages |
Abstract
The Moore bound for a directed graph of maximum out-degree d and diameter k is Md,k=1+d+d2+⋯+dkMd,k=1+d+d2+⋯+dk. It is known that digraphs of order Md,kMd,k (Moore digraphs) do not exist for d>1d>1 and k>1k>1. Similarly, the Moore bound for an undirected graph of maximum degree d and diameter k is Md,k*=1+d+d(d-1)+⋯+d(d-1)k-1. Undirected Moore graphs only exist in a small number of cases. Mixed (or partially directed) Moore graphs generalize both undirected and directed Moore graphs. In this paper, we shall show that all known mixed Moore graphs of diameter k=2k=2 are unique and that mixed Moore graphs of diameter k⩾3k⩾3 do not exist.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Minh Hoang Nguyen, Mirka Miller, Joan Gimbert,