Asymptotic Delsarte cliques in distance-regular graphs
  • Metaadatok
Tartalom: http://real.mtak.hu/44381/
Archívum: MTA Könyvtár
Gyűjtemény: Status = Published
Type = Article
Cím:
Asymptotic Delsarte cliques in distance-regular graphs
Létrehozó:
Babai, László
Wilmes, John
Kiadó:
Springer
Dátum:
2016
Téma:
QA166-QA166.245 Graphs theory / gráfelmélet
Tartalmi leírás:
We give a new bound on the parameter λ (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μ= o(λ2) , then each edge of G belongs to a unique maximal clique of size asymptotically equal to λ, and all other cliques have size o(λ). Here k denotes the degree and μ 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μ= o(λ2) , so families of distance-regular graphs with parameters satisfying kμ= o(λ2) are “asymptotically Delsarte-geometric.” © 2015, Springer Science+Business Media New York.
Nyelv:
angol
magyar
Típus:
Article
PeerReviewed
info:eu-repo/semantics/article
Formátum:
text
text
Azonosító:
Babai, László and Wilmes, John (2016) Asymptotic Delsarte cliques in distance-regular graphs. Journal of Algebraic Combinatorics, 43 (4). pp. 771-782. ISSN 0925-9899, ESSN: 1572-9192
Kapcsolat:
MTMT:3117757; doi:10.1007/s10801-015-0607-0