Abstrakt
A framework for a graph G=(V,E), denoted G(p), consists of an assignment of real vectors p=(p1,p2,...,p|V|) to its vertices. A framework G(p) is called universally completable if for any other framework G(q) that satisfies piTpj=qiTqj for i=j and for edges ij there exists an isometry U such that Uqi=pi for all i.
A graph is called a core if all its endomorphisms are automorphisms. In this work we identify a new sufficient condition for showing that a graph is a core in terms of the universal completability of an appropriate framework for the graph.
To use this condition we develop a method for constructing universally completable frameworks based on the eigenvectors for the smallest eigenspace of the graph. This allows us to recover the known result that the Kneser graph Kn:r and the q-Kneser graph qKn:r are cores for n > = 2r+1.
Our proof is simple and does not rely on the use of an Erdős-Ko-Rado type result as do existing proofs. Furthermore, we also show that a new family of graphs from the binary Hamming scheme are cores, that was not known before.