%0 Journal Article
%T Optimization Problems over Unit-Distance Representations of Graphs
%A Marcel K. de Carli Silva
%A Levent Tun£¿el
%J Mathematics
%D 2010
%I arXiv
%X We study the relationship between unit-distance representations and Lovasz theta number of graphs, originally established by Lovasz. We derive and prove min-max theorems. This framework allows us to derive a weighted version of the hypersphere number of a graph and a related min-max theorem. Then, we connect to sandwich theorems via graph homomorphisms. We present and study a generalization of the hypersphere number of a graph and the related optimization problems. The generalized problem involves finding the smallest ellipsoid of a given shape which contains a unit-distance representation of the graph. We prove that arbitrary positive semidefinite forms describing the ellipsoids yield NP-hard problems.
%U http://arxiv.org/abs/1010.6036v4