In this paper we study the existence of homomorphisms @math using semidefinite programming. Specifically, we use the vector chromatic number of a graph, defined as the smallest real number @math for which there exists an assignment of unit vectors @math to its vertices such that @math when @math . Our approach allows to reprove, without using the Erdős-Ko-Rado Theorem, that for @math the Kneser graph @math and the @math -Kneser graph @math are cores, and furthermore, that for @math there exists a homomorphism @math if and only if @math divides @math . In terms of new applications, we show that the even-weight component of the distance @math -graph of the @math -cube @math is a core and also, that non-bipartite Taylor graphs are cores. Additionally, we give a necessary and sufficient condition for the existence of homomorphisms @math when @math . Lastly, we show that if a 2-walk-regular graph (which is non-bipartite and not complete multipartite) has a unique optimal vector coloring, it is a core. Based on this sufficient condition we conducted a computational study on Ted Spence's list of strongly regular graphs and found that at least 84 are cores.
Standard examples of 1-walk-regular graphs are the @math and their @math -analogs, the @math . These graphs were shown to be UVC in @cite_15 , and for completeness we explicitly give their vector colorings in . We also establish another family of UVC graphs @math (Theorem ). These graphs are constructed from the @math -distance graphs of the @math -cube.
@cite_15
1994392346
Let @math be constant, and let @math denote the set of r-regular graphs with vertex set V = 1,2,...,n . Let G be chosen randomly from @math . We prove that with high probability ( ) the cover time of a random walk on G is asymptotic to @math .