tailieunhanh - Báo cáo toán học: "The Strongly Regular (45, 12, 3, 3) Graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The Strongly Regular (45, 12, 3, 3) Graphs. | The Strongly Regular 45 12 3 3 Graphs Kris Coolsaet Jan Degraer Department of Applied Mathematics and Computer Science Ghent University Krijgslaan 281-S9 B-9000 Gent Belgium Edward Spence Department of Mathematics University of Glasgow Glasgow G12 8QQ Scotland ted@ Submitted May 24 2005 Accepted Mar 24 2006 Published Apr 4 2006 Mathematics Subject Classifications 05E30 05-04 Abstract Using two backtrack algorithms based on different techniques designed and implemented independently we were able to determine up to isomorphism all strongly regular graphs with parameters v 45 k 12 A 1 3. It turns out that there are 78 such graphs having automorphism groups with sizes ranging from 1 to 51840. 1 Introduction A strongly regular graph with parameters v k X ụ denoted by srg v k X ụ is a graph on v vertices that is regular of degree k such that each pair of adjacent vertices has X common neighbours and each pair of non-adjacent vertices has ụ common neighbours. If A denotes the v X v adjacency matrix of such a graph then A2 kl XA ụ J - I - A 1 where as usual I is the identity matrix and J the all-one matrix both of size v. From this it is easily seen that A has three distinct eigenvalues viz. ỠQ k of multiplicity m0 1 and two others Ớ1 Ỡ2 say which are the solutions of x2 ụ X x ụ k 0 of multiplicities m1 and m2 determined by the equations 1 m1 m2 v and k m1ỡ1 m2ỡ2 0. Some authors prefer the notations r ỡ1 s ỡ2 f m1 g m2. To avoid trivial examples we assume that 0 k v 1. Moreover since the THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R32 1 complement of an srg v k X ụ is also an srg v v 1 k v 2k ụ 2 v 2k A we have the further conditions that v 2k ụ 2 0 and v 2k A 0. In addition there is also the condition that k k 1 A ụ v 1 k which is obtained from 1 by multiplying both sides by J. The question of existence and ultimately classihcation of strongly regular graphs satisfying these necessary conditions has occupied .