關鍵詞：強正則圖；半正定規劃；Lasserre 階層。;A strongly regular graph (SRG) with parameters (v， k， λ， μ) is a regular graph with high symmetry. The question of existence for SRGs with a prescribed parameter set is a long-standing and challenging problem in algebraic graph theory. Through the Euclidean representation [1]， the vertices of an SRG are placed in one-to-one correspondence with a spherical two-distance set. Multi-point semidefinite programming (SDP) yields upper bounds on the cardinality of such sets; if the vertex number v of a candidate SRG exceeds the bound， then no SRG with those parameters can exist. Combining Kao and Yu’s distance-distribution constraints [2] with de Laat et al.’s weakened Lasserre dual framework [3]， we produce an efficient SDP verification mechanism.
On Brouwer’s table [4] for v ≤ 1300， there are 4538 candidate parameter sets， 2891 of which remain open. The Krein condition and the absolute bound， two powerful classical methods， together show non-existence for 284 entries in this table. For the existence of SRGs， Delsarte’s linear programming [5] and Bachoc and Vallentin’s semidefinite programming [6] both provide strong constraints， yet neither rules out any parameter set beyond those already eliminated by the Krein condition and the absolute bound. Using a five-point SDP framework with k = 5， we show computationally that every parameter set ruled out by the Krein condition or the absolute bound is also ruled out by five-point SDP， and we show that no SRG exists for two previously open parameter sets， (550， 387， 260， 301) and (703， 520， 372， 420)， both with restricted eigenvalue -3， a case that continues to attract attention [7]. An independently hand-coded five-point version of Kao and Yu’s matrix constraints reaches the same non-existence conclusions for these two cases. This work demonstrates the promise of semidefinite programming in this area.
