- Source: Dot product representation of a graph
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
Media related to Matrix representation of graphs at Wikimedia Commons