Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: PROBLEMS IN ALGEBRAIC COMBINATORICS. | PROBLEMS IN ALGEBRAIC COMBINATORICS C. D. Godsil 1 Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada N2L 3G1 chris@ Submitted July 10 1994 Accepted January 20 1995. Abstract This is a list of open problems mainly in graph theory and all with an algebraic flavour. Except for and they are either folklore or are stolen from other people. AMS Classification Number 05E99 1. Moore Graphs We define a Moore Graph to be a graph with diameter d and girth 2d 1. Somewhat surprisingly any such graph must necessarily be regular see 42 and given this it is not hard to show that any Moore graph is distance regular. The complete graphs and odd cycles are trivial examples of Moore graphs. The Petersen and Hoffman-Singleton graphs are non-trivial examples. These examples were found by Hoffman and Singleton 23 where they showed that if X is a k-regular Moore graph with diameter two then k E 2 3 7 57 . This immediately raises the following question 1 Support from grant OGP0093041 of the National Sciences and Engineering Council of Canada is gratefully acknowledged. THE ELECTRONIC JOURNAL OF COMBINATORICS 2 1995 F1 2 Problem. Is there a regular graph with valency 57 diameter two and girth hve We summarise what is known. Bannai and Ito 4 and independently Damerell 12 showed that a Moore graph has diameter at most two. For an exposition of this see Chapter 23 in Biggs 7 . Aschbacher 2 proved that a Moore graph with valency 57 could not be distance transitive and G. Higman see 9 proved that it could not even be vertex transitive. By either a square-counting or an interlacing argument one can show that the maximum number of vertices in an independent set in the Hoffman-Singleton graph is 15. If S is an independent set of size 15 in this graph then each vertex not in S is adjacent to exactly three vertices in S and so the graph induced by the vertices not in S is 4-regular. This leads to a construction of the Hoffman-Singleton .
