| Popis: |
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 @r(G) of a graph G is the minimum k such that there is a function f:V(G)->R^k 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 R^k. Fiduccia et al. showed that @r(G)@?n/2 for any bipartite graph G on n vertices, and @r(K"m","m)=m. They conjectured that @r(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 @r-critical. |
Full Text from ScienceDirect