Miller, Mirka; Širáň, Jozef

Moore graphs and beyond: a survey of the degree/diameter problem

Electron. J. Comb. DS14, 61 p., electronic only (2005)


Summary: The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. General upper bounds - called Moore bounds - for the order of such graphs and digraphs are attainable only for certain special graphs and digraphs. Finding better (tighter) upper bounds for the maximum possible number of vertices, given the other two parameters, and thus attacking the degree/diameter problem `from above', remains a largely unexplored area.

Mathematics Subject Classification

05C88, 05C89