Eigenvalues and separation in graphs (Q1209408)

If \(f:V(G)\to V(H)\) is a one-to-one map of graphs \(G\) and \(H\), where \(| G|\leq| H|\), then \(\text{sep}(G,H)=\max\min\{\text{dist}_ H(f(x),f(y)):xy\in E(G)\}\) where the maximum is over all such functions \(f\). The study of \(\text{sep}(G,H)\) is an extension of problems arising in coding theory, for example. The authors apply a method involving the Kronecker product to obtain the eigenvalues of powers of the \(n\)-cube \(Q(n)\) and of powers of the discrete torus \(C_ n\times C_ n\). They obtain, among other things, functions \(s(k,p)\) and \(t(k,p)\) such that if \(G\) is a graph with \(p\) points and \(q\) edges, where \(q>s(k,p)\) or \(q>t(k,p)\), then \(\text{sep}(G,Q(n))\leq k\) or \(\text{sep}(G,C_ n\times C_ n)\leq k\).