Optimal Embeddings of Distance Regular Graphs into Euclidean Spaces
Journal of Combinatorial Theory - Series B , Volume 98 p. 95- 104
In this paper we give a lower bound for the least distortion embedding of a distance regular graph into Euclidean space. We use the lower bound for finding the least distortion for Hamming graphs, Johnson graphs, and all strongly regular graphs. Our technique involves semidefinite programming and exploiting the algebra structure of the optimization problem so that the question of finding a lower bound of the least distortion is reduced to an analytic question about orthogonal polynomials.
|, , , ,
|Journal of Combinatorial Theory - Series B
|Semidefinite programming and combinatorial optimization , Spinoza prijs Lex Schrijver
|Networks and Optimization
Vallentin, F. (2008). Optimal Embeddings of Distance Regular Graphs into Euclidean Spaces. Journal of Combinatorial Theory - Series B, 98, 95–104.