Dot product dimensions of graphs

The concept of dot product dimension of graphs was introduced by Fiduccia et al. (1998), as a relaxation of intersection number. The dot product dimension ρ(G) of a graph G is the minimum k such that there is a function f:V(G)→Rk with the property that two distinct vertices u and v are adjacent if and only if f(u)⋅f(v)≥1, where the dot is the standard inner product in Rk. Fiduccia et al. showed that ρ(G)≤n/2 for any bipartite graph G on n vertices, and ρ(Km,m)=m. They conjectured that ρ(G)≤n/2 for any graph G on n vertices. In this paper, we confirm the conjecture for several classes of graphs, and give several necessary conditions for a graph to be ρ-critical.