A dot product representation of a simple graph is a method of representing a graph using vector spaces and the dot product from linear algebra. Every graph has a dot product representation....
Definition Let G be a graph with vertex set V. Let F be a field, and f a function from V to Fk such that xy is an edge of G if and only if f(x)·f(y) ≥ t. This is the dot product representation of G. The number t is called the dot product threshold, and the smallest possible value of k is called the dot product dimension.
Properties A threshold graph is a dot product graph with positive t and dot product dimension 1. Every interval graph has dot product dimension at most 2. Every planar graph has dot product dimension at most 4..
See also Adjacency matrix
References
External links