Discrete Mathematics and Coding Theory Seminars-10All Events

Emre KOLOTOĞLU from Yildiz Technical University will give a talk titled “The Missing Moore Graph" on December 19, 2018, at 15.30 in the room E-2032.

All interested are welcome.

Abstract: The degree-diameter problem, which is suggested by E. F. Moore, is to find, for any given positive integers d and k, a graph with maximum degree d and diameter k with the largest possible number of vertices. Such a graph, if exists, is called a Moore (d, k)-graph. It has been shown in 1960 by A. J. Hoffman and R. R. Singleton that for k = 2, unique graphs exist for d ∈ {2, 3, 7} and possibly for d = 57, but for no other degree. The existence of a Moore (57, 2)-graph is still an open problem. In this talk, I will show part of the proof given by Hoffman and Singleton which exploits the characteristic roots and vectors of the adjacency matrix of the graph. I will also talk about some properties of the automorphism groups of the Moore (d, 2)-graphs for d ∈ {2, 3, 7} and the results obtained about the possible automorphism group of the missing Moore graph.