科研之友
微信
新浪微博
Facebook
分享链接
摘要
We give a new bound on the parameter lambda (number of common neighbors of a pair of adjacent vertices) in a distance-regular graph G, improving and generalizing bounds for strongly regular graphs by Spielman (1996) and Pyber (2014. arXiv: 1409.3041). The new bound is one of the ingredients of recent progress on the complexity of testing isomorphism of strongly regular graphs (Babai et al. 2013). The proof is based on a clique geometry found by Metsch (Des Codes Cryptogr 1(2): 99-116, 1991) under certain constraints on the parameters. We also give a simplified proof of the following asymptotic consequence of Metsch's result: If k mu = o(lambda(2)), then each edge of G belongs to a unique maximal clique of size asymptotically equal to lambda, and all other cliques have size o(lambda). Here k denotes the degree and mu the number of common neighbors of a pair of vertices at distance 2. We point out that Metsch's cliques are "asymptotically Delsarte" when k mu = o(lambda(2)), so families of distance-regular graphs with parameters satisfying k mu = o(lambda(2)) are "asymptotically Delsarte-geometric."
- 出版日期2016-6
