Dot product dimensions of graphs
The concept of dot product dimension of graphs was introduced by Fiduccia etal. (1998), as a relaxation of intersection number. The dot product dimension ?(G) ? ( G ) of a graph G G is the minimum k k such that there is a function f:V(G)?Rk f : V ( G ) ? R k with the property that two distinct vertices u u and v v are adjacent if and only if f(u)?f(v)?1 f ( u ) ? f ( v ) ? 1 , where the dot is the standard inner product in Rk R k . Fiduccia etal. showed that ?(G)?n/2 ? ( G ) ? n / 2 for any bipartite graph G G on n n vertices, and ?(Km,m)=m ? ( K m , m ) = m . They conjectured that ?(G)?n/2 ? ( G ) ? n / 2 for any graph G G on n 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.
dot product dimension k k -dot product representation k k k k k k k -dot product graph k k k k k