Dot product representations of graphs
Charles M. Fiduccia, Edward R. Scheinerman, Ann N. Trenk, Jennifer S. Zito · Discrete Mathematics · 1998
Let k be a positive integer. We call a graph G = (V, E) a k-dot product graph if there is a function ƒ: V → Rκ so that for all vertices v ≠ w we have vw ϵ E if and only if ƒ (v) · ƒ (w) ⩾ 1. The least k for which G is a k-dot product graph is called the dot product dimension of G and is denoted ϱ(G). We discuss the significance of dot product dimension and obtain various results about the dot product dimension of various sorts of graphs.